JRY wants to drag racing along a long road. There are nn sections on the road, the ii-th section has a non-negative integer length sisi. JRY will choose some continuous sections to race (at an unbelievable speed), so there are totally n(n+1)2n(n+1)2 different ways for him to ride. If JRY rides across from the ii-th section to the jj-th section, he would gain j−i+1j−i+1 pleasure. Now JRY wants to know, if he tries all the ways whose length is ss, what's the total pleasure he can get. Please be aware that in the problem, the length of one section could be zero, which means that the length is so trivial that we can regard it as 00.

2

3

1 2 3

4

0 1 2 3

0

1

1

3

0

2

3

1

3

1

6

0

2

7

#include<bits/stdc++.h>

#define ll long long

#define double long double

#define rep(i,x,y) for(int i=x;i<=y;i++)

#define rep2(i,x,y) for(int i=x;i>=y;i--)

using namespace std;

const int maxn=;

const double pi=acos(-1.0);

struct cp

{

    double r,i;

    cp(){}

    cp(double rr,double ii):r(rr),i(ii){}

    cp operator +(const cp&x)const{return cp(r+x.r,i+x.i);}

    cp operator -(const cp&x)const{return cp(r-x.r,i-x.i);}

    cp operator *(const cp&x)const{return cp(r*x.r-i*x.i,i*x.r+r*x.i);}

};

ll ans[maxn];int s[maxn],sum[maxn],R[maxn],n;

cp a[maxn],b[maxn],W,w,p;

void read(int &x){

    x=; char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c>=''&&c<='') x=x*+c-'',c=getchar();

}

inline void fft(cp*c,int t)

{

    int i,j,k;

    for(i=;i<n;i++) R[i]<i?swap(c[R[i]],c[i]),:;

    for(i=;i<n;i<<=)

     for(j=,W={cos(pi/i),sin(pi/i)*t};j<n;j+=i<<)

      for(k=,w={,};k<i;k++,w=w*W)

       p=c[j+k+i]*w,c[j+k+i]=c[j+k]-p,c[j+k]=c[j+k]+p;

}

void solve(int l,int r)

{

    if(l==r){ ans[s[l]]++; return ;}

    int mid=(l+r)>> ,delta=sum[r]-sum[l-];

    solve(l,mid); solve(mid+,r);

    for(n=;(n-)<=delta;n<<=);

    rep(i,,n-) R[i]=R[i>>]>>|(i&?n>>:);

    rep2(i,mid,l) a[sum[mid]-sum[i-]].r+=mid-i+;

    rep(i,mid+,r) ++b[sum[i]-sum[mid]].r;

    fft(a,); fft(b,);

    rep(i,,n-) a[i]=a[i]*b[i];

    fft(a,-);

    rep(i,,delta) ans[i]+=(ll)((a[i].r)/n+0.5);

    rep(i,,n) a[i]=b[i]=cp(.,.);

    rep2(i,mid,l) ++a[sum[mid]-sum[i-]].r;

    rep(i,mid+,r) b[sum[i]-sum[mid]].r+=i-mid;

    fft(a,); fft(b,);

    rep(i,,n-) a[i]=a[i]*b[i];

    fft(a,-);

    rep(i,,delta) ans[i]+=(ll)((a[i].r)/n+0.5);

    rep(i,,n) a[i]=b[i]=cp(.,.);

}

int main()

{

    int N,T;

    scanf("%d",&T);

    while(T--){

        read(N);

        rep(i,,N) read(s[i]),sum[i]=sum[i-]+s[i];

        rep(i,,sum[N]) ans[i]=;

        solve(,N);

        rep(i,,sum[N]) printf("%lld\n",ans[i]);

    }

    return ;

}