You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 128.0 MB

Description

Roy and Emon are playing an interesting game which is called flipping game. There are N index on the board. Each index has assigned a character either 0 or 1.
In each turn, one of them must select exactly one index \(i\), \(1<=i<=N\) from the board, which one previously not used by anyone. After select \(i_{th}\) index, flip its character (if current \(i_{th}\) index character is 0, flip it into 1 or vice versa). They selecting index until there is no unused index remaining on the board.

Roy wants to maximize consecutive 1, where Emon wants to minimize it. Roy starts the game.

For example, after finishing the game if board looks like, "1011011101", then maximum consecutive 1 is 3.

If they play optimally, find the maximum consecutive 1 on the board after finishing the game?

Input

First line T, the number of test cases.
In each test case, first line N the length of the string.
Second line, a string S , the length of the string is N.

\(1<=T<=10^4\)
\(1<=N<= 2 * 10^5\)
String S contains only 0 and 1.
Sum of N overall test case doesn't exceed \(2 * 10^5\).

Output

In each test case, print the maximum consecutive 1 on the board.

Sample

2
2
10
3
010

1
1