Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

data structures

dp

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. BinaryStringForces

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$.

Input

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

Output

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

Example

Input

4610001131015111116010101

Output

8 5 15 18

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2024 01:10:03 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|