Problem B: Perfect substring

Problem B: 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

HINT

[Submit][Status]