CF1693F I Might Be Wrong

You 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.

The 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 $ .

For each test case, output the minimum total number of coins required to sort $ S $ in increasing order.

In 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 $ .