Background

"qjyxfgms" is very likely an abbreviation made from the initial letters of Chinese pinyin. A common interpretation is: "请假一下发给秘书" ("qing jia yi xia fa gei mi shu", meaning "Please ask for leave and send it to the secretary".).

Problem Description

You are given a 01 sequence $a$ of length $n$.

You can perform several operations on this sequence. In each operation, you may choose a position $i(1\le i\le n-2)$, and assign $a_i,a_{i+1},a_{i+2}$ to $mex(\{a_i,a_{i+1},a_{i+2}\})$.

You need to find the minimum number of operations to make all positions become $0$.

Here, $mex(S)$ denotes the smallest natural number that does not appear in the set $S$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, denoting the number of test cases. For each test case:

• The first line contains a positive integer $n$.
• The second line contains $n$ integers $a_1, \ldots, a_n$, where $a_i\in\{0,1\}$.

Output Format

For each test case, output one line with a non-negative integer, representing the answer.

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

3
3

Hint

[Sample Explanation #1]

For the first test case:

• In the $1$st operation, choose position $3$. Since $mex(\{a_3,a_4,a_5\})=mex(\{0,1,0\})=2$, the sequence becomes $[1,1,2,2,2,1]$.
• In the $2$nd operation, choose position $1$. Since $mex(\{a_1,a_2,a_3\})=mex(\{1,1,2\})=0$, the sequence becomes $[0,0,0,2,2,1]$.
• In the $3$rd operation, choose position $4$. Since $mex(\{a_4,a_5,a_6\})=mex(\{2,2,1\})=0$, the sequence becomes $[0,0,0,0,0,0]$.

In total, $3$ operations are used to make all positions become $0$. It can be proven that no solution with fewer operations exists.

[Constraints]

This problem uses bundled tests.

For all test cases, it is guaranteed that:

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

::cute-table{tuack}

Special Property A: $\sum n^3\le 3\times 10^7$.

Special Property B: $\sum n^2\le 3\times 10^7$.

Special Property C: it is guaranteed that the number of positions $i$ satisfying $a_i=0$ does not exceed $15$.

Translated by ChatGPT 5