C. Good Subarrays

time limit per test

2 seconds

memory limit per test

256 megabytes

You are given an array a1,a2,…,ana1,a2,…,an consisting of integers from 00 to 99. A subarray al,al+1,al+2,…,ar−1,aral,al+1,al+2,…,ar−1,ar is good if the sum of elements of this subarray is equal to the length of this subarray (∑i=lrai=r−l+1∑i=lrai=r−l+1).

For example, if a=[1,2,0]a=[1,2,0], then there are 33 good subarrays: a1…1=[1],a2…3=[2,0]a1…1=[1],a2…3=[2,0] and a1…3=[1,2,0]a1…3=[1,2,0].

Calculate the number of good subarrays of the array aa.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains one integer nn (1≤n≤1051≤n≤105) — the length of the array aa.

The second line of each test case contains a string consisting of nn decimal digits, where the ii-th digit is equal to the value of aiai.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

For each test case print one integer — the number of good subarrays of the array aa.

Example

Input

Copy

3
3
120
5
11011
6
600005

Output

Copy

3
6
1

Note

The first test case is considered in the statement.

In the second test case, there are 66 good subarrays: a1…1a1…1, a2…2a2…2, a1…2a1…2, a4…4a4…4, a5…5a5…5 and a4…5a4…5.

In the third test case there is only one good subarray: a2…6a2…6.

解题说明：此题是一道数列题，确保区间内每个元素的和为区间长度。因为区间和等于前缀和相减即sum[i]−sum[j−1]。所以由题意可以得到：sum[i]−sum[j−1]=i−j+1。移项后得：sum[i]−i=sum[j−1]−j+1。统计 sum[i]−i的个数即可。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<map>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const ll mm = 1e5 + 60;
ll s[mm], n, ans;
map<ll, ll>mp;int main()
{int t;cin >> t;while (t--){memset(s, 0, sizeof(s));ans = 0;mp.clear();mp[0] = 1;cin >> n;for (int i = 1; i <= n; i++){char c;cin >> c;s[i] = s[i - 1] + c - '0';ans += mp[s[i] - i]++;}cout << ans << endl;}return 0;
}