Gym

The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case.

He is given a string of zeros and ones and length N.

Let F(x, y) equal to the number of ones in the string between indices x and yinclusively.

Your task is to help Sherlock Bones find the number of ways to choose indices (i, j, k) such that i < j < k, s_j is equal to 1, and F(i, j) is equal to F(j, k).

Input

The first line of input is T – the number of test cases.

The first line of each test case is an integer N (3 ≤ N ≤ 2 × 10⁵).

The second line is a string of zeros and ones of length N.

Output

For each test case, output a line containing a single integer- the number of ways to choose indices (i, j, k).

Example

Input

Outpu2

3
7

题意：
给定01字符串，求有多少个三元组i,j,k满足i<j<k且F(i, j)=F(j, k).其中F（x,y）是字符串下标x到y的一的个数。
下标为j的一定要是1。
思路：
先处理一下0的数量分布。比如00110就是2,0,1
假设字符串以0为开头和结尾，那么字符串便可以表示为：
a,1,b,1,c,1,d,1,e,1,f
其中字母表示0的数量。
枚举j在哪一个1上，便可以得出以下式子、
ans=a*b+  b*c+a*d+  c*d+b*e+a*f+  d*e+c*f+  e*f;
可以看出，每一个字母其实就是要与之后奇数或偶数的后缀和相乘，乘积相加就是结果。
但是这样仍然不对，因为i可k还可以指向1.
于是我们把每个字母的值加上一个1，再进行计算即可。
然而这样还是有问题。
相邻的两个字母相乘时不需要+1，于是我们再用一个for循环处理一下即可。

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 200086;
const int inf = 2.1e9;
const ll Inf = 999999999999999999;
const int mod = 1000000007;
const double eps = 1e-6;
const double pi = acos(-1);
char s[maxn];
vector<ll>v;
ll sum[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){int len;
        scanf("%d%s",&len,s);
        memset(sum,0,sizeof(sum));
        v.clear();
        ll ans=1;
        for(int i=0;i<len;i++){
            if(s[i]=='0'){
                ans++;
            }
            else{
                v.push_back(ans);
                ans=1;
            }
        }
        v.push_back(ans);
        int sz=v.size();
        for(int i=sz-1;i>=0;i--){
            sum[i]=v[i]+sum[i+2];
        }
        ans=0;
        for(int i=0;i<sz;i++){
            ans+=v[i]*sum[i+1];
        }
        for(int i=0;i<sz-1;i++){
            ans-=v[i]*v[i+1]-(v[i]-1)*(v[i+1]-1);
        }
        printf("%lld
",ans);
    }
    return 0;
}

View Code