도시 점령

JB는 게임을 하고 있다. 게임에는 $n$개의 도시가 있으며, 번호는 $1, 2, \cdots, n$이다. $i$번 도시와 $j$번 도시는 $i = j - 1$ 또는 $i = j + 1$일 때만 인접한다. 처음에 일부 도시는 JB가 차지하고 있다.

게임은 라운드 단위로 진행된다. 라운드가 시작될 때 점령된 각 도시는 인접한 미점령 도시 중 최대 하나를 공격 대상으로 표시할 수 있다. 라운드가 끝나면 표시된 공격 대상이 모두 점령된다. 모든 도시가 점령되면 게임이 끝난다.

JB는 최소한의 라운드로 모든 도시를 점령하려고 한다. 그를 도와줄 수 있겠는가?

테스트 케이스는 여러 개 주어진다. 첫 줄에는 테스트 케이스의 수를 나타내는 양의 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 도시의 수 $n$ ($1 \le n \le 10^6$)이 주어진다.

다음 줄에는 길이가 $n$인 문자열 $s$가 주어진다. $s$는 '0'과 '1'로만 이루어져 있다. $s$의 $i$번째 문자는 $i$번 도시의 처음 상태를 나타낸다. $s_i$가 '1'이면 $i$번 도시는 처음에 JB가 점령하고 있고, 그렇지 않으면 점령하고 있지 않다.

모든 테스트 케이스의 $n$을 합한 값은 $10^6$을 넘지 않는다. $s$에는 '1'이 적어도 하나 있다.

각 테스트 케이스마다 모든 도시를 점령하는 데 필요한 최소 라운드 수를 한 줄에 출력한다.

두 번째 테스트 케이스에서는 $0100 \rightarrow 0110 \rightarrow 1111$ 순서로 점령하는 것이 가장 좋다.