F. I Might Be Wrongtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a binary string S of length n indexed from 1 to n. You can perform the following operation any number of times (possibly zero):Choose two integers l and r (1 \le l \le r \le n). Let cnt_0 be the number of times 0 occurs in S[l \ldots r] and cnt_1 be the number of times 1 occurs in S[l \ldots r]. You can pay |cnt_0 - cnt_1| + 1 coins and sort the S[l \ldots r]. (by S[l \ldots r] we mean the substring of S starting at position l and ending at position r)For example if S =  11001, we can perform the operation on S[2 \ldots 4], paying |2 - 1| + 1 = 2 coins, and obtain S =  10011 as a new string.Find the minimum total number of coins required to sort S in increasing order.InputThe first line contains a single integer t (1 \le t \le 1000) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer n (1 \le n \le 2 \cdot 10^5) — the size of S.The second line of each test case contains a binary string S of n characters S_1S_2 \ldots S_n. (S_i =  0 or S_i =  1 for each 1 \le i \le n)It is guaranteed that the sum of n over all test cases doesn't exceed 2 \cdot 10^5.OutputFor each test case, output the minimum total number of coins required to sort S in increasing order.ExampleInput
71121031014100051101061100002001000010001010011000Output
0
1
1
3
2
2
5
NoteIn the first test case, S is already sorted.In the second test case, it's enough to apply the operation with l = 1, r = 2.In the third test case, it's enough to apply the operation with l = 1, r = 2.
71121031014100051101061100002001000010001010011000
0 1 1 3 2 2 5 
['binary search', 'greedy', 'two pointers', '*3400']