题目描述

给定一个长度为 $n$ 的数组 $a$，数组仅包含数字 $1,2,3$。可以对数组执行若干次以下操作，每次任选一位置进行：

• 若在位置 $i$ 处的值为 $1$，可以把该位置的值变为 $0$ 并获得 $1$ 分，同时把与位置 $i$ 相邻的两个位置变为 $0$（若越界则忽略该侧）。
• 若在位置 $i$ 处的值为 $2$，可以把该位置的值变为 $0$ 并获得 $2$ 分，同时把与位置 $i$ 相邻的两个位置变为 $0$（若越界则忽略该侧）。
• 若在位置 $i$ 处的值为 $3$，可以把该位置的值变为 $0$ 并获得 $3$ 分，同时把与位置 $i$ 相邻的两个位置变为 $0$（若越界则忽略该侧）。

可以重复执行上述操作任意次，但同一位置一旦变为 $0$ 再不能得分。求能够获得的最大总分。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试组数。

接下来为 $t$ 组数据，每组数据格式如下：

• 一行一个整数 $n$，表示数组长度。
• 一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，数组元素且每个 $a_i \in \{1,2,3\}$。

保证所有测试数据中各组的 $n$ 之和不超过题目给定的数据范围。

输出格式

对每组测试数据输出一行包含一个整数 —— 能够获得的最大总分。

样例输入

1
5
1 2 1 3 1

样例输出

5

说明

样例解释

对样例数组 $[1,2,1,3,1]$，可以选择位置 $2$（值为 $2$）得 $2$ 分，位置 $4$（值为 $3$）得 $3$ 分，合计 $5$ 分，其余位置被置 $0$ 后无法再得分，$5$ 为最大可能得分。

数据范围