A pandemic is raging in Byteotia! The spreading SPLAY-CRT-2 virus (colloquially known as the Kruskalovirus) threatens the health of the citizens. Fortunately, the brightest minds in Byteotia have quickly invented an effective vaccine. However, this is not the end of the problems – now, vaccinations must be planned.

Byteotia consists of $n$ cities numbered from $1$ to $n$. The cities are located along a single main road; thus, for every $i$ ($1 \le i \le n - 1$), the cities numbered $i$ and $i+1$ are adjacent to each other.

Each city is initially either completely free of the virus or all of its inhabitants are infected. Every day, the Byteotian health service can vaccinate all inhabitants of one arbitrarily chosen city, provided that it is not yet taken over by the plague. Unfortunately, every night, every unvaccinated city that was previously free of the disease but is adjacent to a city taken over by the virus becomes infected. The vaccination process in Byteotia begins in the morning: first, the health service can vaccinate one city, and only then does the virus begin to spread.

Your task is to plan the vaccinations such that when the situation in Byteotia stabilizes (i.e., every city is either infected with the virus or vaccinated), the number of infected cities is as small as possible.

Help the citizens of Byteotia and calculate how many cities will be infected under an optimal vaccination strategy.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^5$), denoting the number of test cases.

The next $2t$ lines contain descriptions of the test cases. Each consists of two lines. The first contains a single integer $n$ ($1 \le n \le 10^5$), denoting the number of cities in Byteotia. The second contains a string of $n$ characters, either '0' or '1'. If the $i$-th character is '1', the $i$-th city is initially infected with the virus; otherwise, it is free of the disease.

The sum of $n$ over all test cases does not exceed $10^6$.

Output

The output should contain $t$ lines. The $i$-th line should contain a single integer representing the minimum possible number of infected cities in the $i$-th test case.

Examples

Input 1

3
8
00110100
10
1001000010
4
0000

Output 1

5
7
0

Note

In the first test case, we can first vaccinate the inhabitants of the second city. During the night, the plague will spread to cities 5 and 7. On the second day, we can vaccinate the inhabitants of the eighth city. The pandemic is then contained. Only city 1 remains to be vaccinated. In this way, 5 cities (numbered 3, 4, 5, 6, and 7) will be infected. It can be proven that this is the optimal result.

In the second test case, we can vaccinate the cities in the order 8, 6, and 7.

In the last test case, there is no virus in Byteotia at all, so all cities can be vaccinated in any order.*

*You might wonder why one would vaccinate the citizens of Byteotia at all if there is no virus there. However, it cannot be ruled out that it might arrive from other countries in the future, so it is worth taking preventive care of the citizens' health.