How Many Maximums

 From an array $A$ containing $N$ integers, you construct a binary string $S$ of length $(N - 1)$ as follows. For all $1 \le i \lt N$:

• If $A_i < A_{i+1}$, then $S_i = 0$.
• If $A_i > A_{i+1}$, then $S_i = 1$.

Given the string $S$, determine the count of indices $i$ $(1 \le i \le N)$ such that it is possible for $A_i$ to be the maximum element of the array $A$.

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the size of the array $A$.
• The second line of each test case contains the binary string $S$ of length $(N - 1)$ containing $0$s and $1$s only.

Output Format

For each test case, output the count of indices $i$ $(1 \le i \le N)$ such that it is possible for $A_i$ to be the maximum element of the array $A$.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 10^5$
• Sum of $N$ over all test cases does not exceed $10^5$.

Sample Input 1 

3
2
0
7
000111
6
11100

Sample Output 1 

1
1
2

Explanation

Test case $1$: Here $A_1 \lt A_2$. Therefore clearly only $A_2$ can be the maximum element of $A$.

Test case $2$: Here $A_1 \lt A_2$, $A_2 \lt A_3$, $A_3 \lt A_4$, $A_4 \gt A_5$, $A_5 \gt A_6$ and $A_6 \gt A_7$. Therefore, clearly only $A_4$ can be the maximum element of $A$.

Test case $3$: Here $A_1 \gt A_2$, $A_2 \gt A_3$, $A_3 \gt A_4$, $A_4 \lt A_5$ and $A_5 \lt A_6$. Therefore $A_1$ and $A_6$ both can be the maximum elements of $A$.