PRI3: Disturbed People // Intermediate

There is a house with $n$ flats situated on the main street of the Shire. George is watching this house every night. The house can be represented as an array of $n$ integer numbers $a_1, a_2, ..., a_n$ where $a_i = 1$ if the light in the $i^{th}$ flat is on and $a_i = 0$ otherwise.

George thinks that a person in the $i^{th}$ flat is disturbed and cannot sleep if and only if $1 < i < n$ and $a_{i-1} = a_{i+1} = 1$ and $a_i = 0$.

George is concerned by the following question: what is the minimum number $k$ such that if people from exactly $k$ pairwise distinct flats will turn off the lights then nobody will be disturbed? Your task is to find this number $k$.

Input Format

The first line contains the number of test cases, $t$.

In each test case:

The first line of the input contains one integer $n$ ($3 \leq n \leq 100$) — the number of flats in the house.

The second line of the input contains $n$ integers $a_1, a_2, ..., a_n$, where $a_i$ is the state of the light in the $i^{th}$ flat ($a_i$ is either $0$ for off or $1$ for on).

Sample Input

2
10
1 1 0 1 1 0 1 0 1 0
5
1 1 0 0 0

Output Format

For each test case, print only one integer — the minimum number $k$ such that if people from exactly $k$ pairwise distinct flats turn off the light then nobody will be disturbed.

Sample Output

2
0