M. Tactical Game
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp plays a computer game — a tactical RPG, to be specific. Right now, he has to defeat several enemies to win the current battle.

The enemy side of the battlefield can be represented as a row of $$$n$$$ cells, numbered from $$$1$$$ to $$$n$$$ from left to right. Every cell is either empty (represented by the character '0'), or contains an enemy (represented by the character '1').

To win the battle, Monocarp can perform the following actions:

  • choose an enemy which is not eliminated yet and cast a lightning bolt at that enemy, instantly eliminating them;
  • choose an enemy which is not eliminated yet and launch a fireball at that enemy. The fireball's explosion eliminates both the target and the adjacent enemies (if there are any). Formally, if the fireball is launched at the enemy in the cell $$$i$$$, the enemies in the cells $$$(i-1)$$$ and $$$(i+1)$$$, if they exist, are also eliminated. Note that a fireball can be launched only at an enemy; Monocarp cannot launch a fireball at an empty cell.

Of course, fireballs are more efficient; however, Monocarp can launch at most one fireball during the battle. Thankfully, he can cast the lightning bolt any number of times.

Your task is to help Monocarp determine the minimum number of actions he has to perform in order to eliminate all enemies.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of cells.

The second line of each test case contains one string $$$s$$$ ($$$|s| = n$$$). Each character of $$$s$$$ is either '0' (if the corresponding cell is empty) or '1' (if the corresponding cell contains an enemy).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print one integer — the minimum number of actions Monocarp has to perform in order to eliminate all enemies.

Example
Input
4
5
00000
7
1010101
8
01110110
9
110101100
Output
0
4
3
4