You are given a binary stringof length .
You have to perform the following operation exactly once:
- Select an index and delete from . The remaining parts of are concatenated in the same order.
How many distinct binary strings of lengthcan you get after applying this operation?
- The first line of input contains a single integer – the number of test cases. The description of test cases follow.
- The first line of each test case contains – the length of the binary string .
- The second line contains the binary string .
For each test case, output the number of distinct binary strings that you can get after applying the operation exactly once.
- Sum of does not exceed over all testcases.
Sample Input 1
3 3 100 4 1111 5 10110
Sample Output 1
2 1 4
Test Case 1: We have. Now, we can get (on deleting ), (on deleting ) and (on deleting ). Therefore, we can get distinct strings.
Test Case 2: We have. Now, we will always get irrespective of the index on which we apply the operation. Therefore, we can get distinct string.