Minimum Contiguous Substrings

Given a binary string s of length n, you are allowed to rearrange the characters in any order. By rearranging the string, your task is to determine the minimum number of contiguous substrings consisting entirely of the character 1 needed to cover all 1's. In other words, if the string contains at least one 1, you can always rearrange it so that all 1's are consecutive, forming one contiguous substring. However, if the string does not contain any 1, then the answer is 0.

The problem can be formally stated as follows. Given an integer \( T \) representing the number of test cases, and for each test case an integer \( n \) followed by a binary string \( s \) of length \( n \), determine:

[ \text{answer} = \begin{cases} 1, & \text{if } s \text{ contains at least one } 1,\ 0, & \text{if } s \text{ does not contain any } 1. \end{cases} ]

inputFormat

The first line contains an integer \( T \) (\(1 \le T \le 10^5\)) denoting the number of test cases. Each test case consists of a line containing an integer \( n \) (length of the binary string) and a binary string \( s \) (consisting only of characters 0 and 1) separated by a space.

outputFormat

For each test case, print a single line with the minimum number of contiguous substrings that contain only 1's after optimal rearrangement of the string.

## sample

3
5 10101
4 1100
6 111000

1
1
1

</p>