## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] How Many Maximums CodeChef Solution | CodeChef Problem Solution 2022

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

• 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$ $\left(1\le i\le N\right)$ 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 $\left(N-1\right)$ containing $0$s and $1$s only.

### Output Format

For each test case, output the count of indices $i$ $\left(1\le i\le N\right)$ such that it is possible for ${A}_{i}$ to be

the maximum element of the array $A$.

### Constraints

• $1\le T\le {10}^{5}$
• $2\le N\le {10}^{5}$
• Sum of $N$ over all test cases does not exceed