说明

给出长度为 $n$ 的 01 序列 $a$。

你可以对这个序列进行若干次操作。每次操作可以选择一个位置 $i(1\le i\le n-2)$，并将 $a_i,a_{i+1},a_{i+2}$ 赋值为 $mex(\{a_i,a_{i+1},a_{i+2}\})$。

你需要求出，使得所有位置都变成 0 的最小操作次数。

其中 $mex(S)$ 表示集合 $S$ 中最小未出现过的自然数。

输入格式

本题包含多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。对于每组测试数据：

• 第一行，一个正整数 $n$。
• 第二行，$n$ 个整数 $a_1, \ldots, a_n$，其中 $a_i\in\{0,1\}$。

输出格式

对于每组测试数据，输出一行，一个非负整数，表示答案。

2
6
1 1 0 1 0 1
4
1 1 1 1

3
3

提示

【样例解释 #1】

对于第一组测试数据：

• 第 $1$ 次操作选择位置 $3$，其中 $mex(\{a_3,a_4,a_5\})=mex(\{0,1,0\})=2$，序列变为 $[1,1,2,2,2,1]$；
• 第 $2$ 次操作选择位置 $1$，其中 $mex(\{a_1,a_2,a_3\})=mex(\{1,1,2\})=0$，序列变为 $[0,0,0,2,2,1]$；
• 第 $3$ 次操作选择位置 $4$，其中 $mex(\{a_4,a_5,a_6\})=mex(\{2,2,1\})=0$，序列变为 $[0,0,0,0,0,0]$；

总共使用 $3$ 次操作使得所有位置都变成 0。可以证明不存在次数更少的操作方案。

【数据范围】

本题采用捆绑测试。

对于所有测试数据，保证：

• $1\le T\le 10^6$；
• $3\le n,\sum n\le 10^6$；
• $a_i\in\{0,1\}$。

::cute-table{tuack}

特殊性质 A：$\sum n^3\le 3\times 10^7$；

特殊性质 B：$\sum n^2\le 3\times 10^7$；

特殊性质 C：保证满足 $a_i=0$ 的位置 $i$ 数量不超过 $15$；