There are N doors numbered 1 to N some of which are initially open while the rest are closed. Starting from time t = 1, you can choose to assign one guard per second at any position who moves from left to right and inverts the door's current state. Formally, if a guard is assigned to position i at time t, he performs operations on doors i,i+1...N at time t,t+1...t+(N-i). Each guard's operations are independent of each other.
Assuming that the guards are assigned at optimal positions, what is the minimum time at which all doors can be open simultaneously?
INPUT FORMAT
First line contains T, the number of test cases.
Each test case contains two lines.
First line contains N, the number of doors.
Second line contains a binary string of length N, where 0 denotes that the door is initially closed and 1 denotes that the door is initially open.
OUTPUT FORMAT
Print the minimum time at which all doors can be open simultaneously for each test case.
CONSTRAINTS
1≤T≤5
1≤N≤16
