CF1750H BinaryStringForces

You are given a binary string $ s $ of length $ n $ . We define a maximal substring as a substring that cannot be extended while keeping all elements equal. For example, in the string $ 11000111 $ there are three maximal substrings: $ 11 $ , $ 000 $ and $ 111 $ . In one operation, you can select two maximal adjacent substrings. Since they are maximal and adjacent, it's easy to see their elements must have different values. Let $ a $ be the length of the sequence of ones and $ b $ be the length of the sequence of zeros. Then do the following: - If $ a \ge b $ , then replace $ b $ selected zeros with $ b $ ones. - If $ a < b $ , then replace $ a $ selected ones with $ a $ zeros. As an example, for $ 1110000 $ we make it $ 0000000 $ , for $ 0011 $ we make it $ 1111 $ . We call a string being good if it can be turned into $ 1111...1111 $ using the aforementioned operation any number of times (possibly, zero). Find the number of good substrings among all $ \frac{n(n+1)}{2} $ non-empty substrings of $ s $ .

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the string $ s $ . The second line of each test case contains the binary string $ s $ of length $ n $ . It is guaranteed that sum of $ n $ across all test cases doesn't exceed $ 2 \cdot 10^5 $ .

For each test case, print a single integer — the number of good substrings.

Let's define a substring from index $ l $ to index $ r $ as $ [l, r] $ . For the first test case, the good substrings are: - $ [1,1] $ , - $ [1,2] $ , - $ [3,6] $ , - $ [4,5] $ , - $ [4,6] $ , - $ [5,5] $ , - $ [5,6] $ , - $ [6,6] $ . In the second test case, all substrings are good except $ [2,2] $ . In the third test case, all substrings are good.