You are given an array $a_1, a_2, \dots , a_n$ consisting of integers from $0$ to $9$. A subarray $a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r$ is good if the sum of elements of this subarray is equal to the length of this subarray ($\sum\limits_{i=l}^{r} a_i = r - l + 1$).

For example, if $a = [1, 2, 0]$, then there are $3$ good subarrays: $a_{1 \dots 1} = [1], a_{2 \dots 3} = [2, 0]$ and $a_{1 \dots 3} = [1, 2, 0]$.

Calculate the number of good subarrays of the array $a$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line of each test case contains a string consisting of $n$ decimal digits, where the $i$-th digit is equal to the value of $a_i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

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


-----Example-----
Input
3
3
120
5
11011
6
600005

Output
3
6
1



-----Note-----

The first test case is considered in the statement.

In the second test case, there are $6$ good subarrays: $a_{1 \dots 1}$, $a_{2 \dots 2}$, $a_{1 \dots 2}$, $a_{4 \dots 4}$, $a_{5 \dots 5}$ and $a_{4 \dots 5}$. 

In the third test case there is only one good subarray: $a_{2 \dots 6}$.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n = int(input())
    s = input()

    d = {0: 1}
    summa, cnt = 0, 0
    ans = 0
    for i in s:
        summa += int(i)
        cnt += 1

        k = cnt - summa
        if k not in d:
            d[k] = 0
        ans += d[k]
        d[k] += 1

    print(ans)


import sys
input = sys.stdin.readline
from collections import Counter

t=int(input())
for tests in range(t):
    n=int(input())
    A=input().strip()

    L=[]
    for a in A:
        L.append(int(a)-1)

    SUM=[0]
    for l in L:
        SUM.append(SUM[-1]+l)

    #print(SUM)

    C=Counter(SUM)

    ANS=0

    for c in C:
        ANS+=C[c]*(C[c]-1)//2

    print(ANS)
        


import sys

input=sys.stdin.readline

for _ in range(int(input())):
    n=int(input())
    s=input()
    a=[int(s[i])-1 for i in range(n)]
    data=[0]+a
    for i in range(1,n+1):
        data[i]+=data[i-1]
    dic={}
    for i in range(n+1):
        if data[i] not in dic:
            dic[data[i]]=0
        dic[data[i]]+=1
    ans=0
    for d in dic:
        ans+=dic[d]*(dic[d]-1)//2
    print(ans)


from collections import defaultdict

def solve():
    n = int(input())
    a = list(map(int, input()))
    s = [0] * (n + 1)
    for i in range(n):
        s[i + 1] = s[i] + a[i] - 1
    t = defaultdict(int)
    t[s[0]] += 1
    ans = 0
    for i in range(1, n + 1):
        ans += t[s[i]]
        t[s[i]] += 1
    print(ans)

t = int(input())
for _ in range(t):
    solve()

T, = list(map(int, input().split()))
for t in range(T):
    N, = list(map(int, input().split()))
    X = [0]*(N+1)
    for i, c in enumerate(input().strip()):
        X[i+1] = X[i]+int(c)
    d = dict()
    for i in range( N+1):
        x = X[i] - i
        if x not in d:
            d[x] = 0
        d[x] += 1
    R = 0
    for k in d:
        R += d[k]*(d[k]-1)//2
    print(R)


t=int(input())
for you in range(t):
    n=int(input())
    l=input()
    hashi=dict()
    hashi[0]=1
    count=0
    sumi=0
    for i in range(n):
        sumi=sumi+(int(l[i]))
        z=sumi-(i+1)
        if(z in hashi):
            count=count+hashi[z]
            hashi[z]+=1
        else:
            hashi[z]=1
    print(count)


q = int(input())
for _ in range(q):
    n = int(input())
    s = list(input())
    s = list(map(int,s))
    l = [s[i] - 1 for i in range(n)]
    pref = [0] * (n+1)
    for i in range(1,n+1):
        pref[i] = pref[i-1] + l[i-1]
    d = {}
    for elt in pref:
        try:
            d[elt] += 1
        except Exception:
            d[elt] = 1
    wyn = 0
    for elt in d:
        wyn += (d[elt]*(d[elt]-1)//2)
    print(wyn)

from collections import defaultdict as dd
import math
import sys
input=sys.stdin.readline
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))


def solve():
	n=nn()
	l = input()
	seen = dd(int)
	seen[0] = 1
	tally = 0
	good= 0
	for i in range(n):
		tally+=int(l[i])-1
		seen[tally]+=1

	total = 0

	for s in seen:
		total+=(seen[s]*(seen[s]-1)//2)

	print(total)


q=nn()
for _ in range(q):
	solve()