[Solution] BinaryStringForces Codeforces Solution

H. BinaryStringForces

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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$11000111$ there are three maximal substrings: 11$11$, 000$000$ and 111$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$1110000$ we make it 0000000$0000000$, for 0011$0011$ we make it 1111$1111$. We call a string being good if it can be turned into 1111...1111$\mathrm{1111...1111}$ using the aforementioned operation any number of times (possibly, zero). Find the number of good substrings among all 𝑛(𝑛+1)2$\frac{n(n+1)}{2}$ non-empty substrings of 𝑠$s$.

Input

Each test consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤105$1\le t\le {10}^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains 𝑛$n$ (1≤𝑛≤2⋅105$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⋅105$2\cdot {10}^5$.

Output

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

Note

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,1]$,
• [1,2]$[1,2]$,
• [3,6]$[3,6]$,
• [4,5]$[4,5]$,
• [4,6]$[4,6]$,
• [5,5]$[5,5]$,
• [5,6]$[5,6]$,
• [6,6]$[6,6]$.

In the second test case, all substrings are good except [2,2]$[2,2]$.

In the third test case, all substrings are good.