Occupy the Cities

JB is playing a game. The game has $n$ cities, numbered $1, 2, \cdots, n$. The $i$-th and $j$-th cities are adjacent if and only if $i = j - 1$ or $i = j + 1$. Initially, some of the cities are occupied by JB.

The game runs in rounds. At the start of a round, each occupied city can mark at most one adjacent unoccupied city as its attack target. At the end of the round, all marked attack targets become occupied. The game ends when all the cities are occupied.

JB wants to occupy all the cities in the minimum number of rounds. Can you help him?

There are multiple test cases. The first line contains a positive integer $T$, the number of test cases. Each test case is as follows.

The first line contains an integer $n$ ($1 \le n \le 10^6$), the number of cities.

The next line contains a string $s$ of length $n$, consisting only of '0' and '1'. The $i$-th character describes the initial state of the $i$-th city: if $s_i$ is '1', the $i$-th city is initially occupied by JB. Otherwise, it is not.

The sum of $n$ over all test cases does not exceed $10^6$. At least one '1' is in $s$.

For each test case, output one line containing the minimum number of rounds needed to occupy all the cities.

In the second test case, the best way is $0100 \rightarrow 0110 \rightarrow 1111$.