13021302 SUSTech Online Judge
Problem 1302 --Perfect substring

## 1302: Perfect substring

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 73  Solved: 23
[Submit][Status][Web Board]

## Description

Pisces likes 0s! In his opinion, 0 is the ultimate of everything and the eternal answer to all questions. He thinks a string is perfect if it only contains 0s. Now given a binary string of length $$n$$, Pisces wants to know how many perfect substrings it has.

## Input

The first line contains an integer $$T(1\leq T\leq 10)$$, which represents the number of test cases.

For each of the test case, the first line is an integer $$n(1\leq n\leq 10^5)$$, which is the length of the given string. The second line is a binary string of length $$n$$.

## Output

For each test case, print the number of perfect substrings in the given string.

## Sample Input

2
6
001100
6
010101

## Sample Output

6
3

[Submit][Status]