Shaun is very much interested in Subarrays. Shaun wants to count the number of subarrays in his chosen array with sum being a multiple of $10^9$. Since, Shaun is interested in huge numbers.He chose his array such that it contains only $10^8$ and $9*10^8$ as its elements.
Help shaun to count the number of required subarrays.
-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each testcase contains one integer $N$,size of array $A$. 
- Second line of each testcase contains $N$ space separated array elements
-----Output:-----
For each testcase, output in a single line number of subarrays with sum being multiple of $10^9$.
-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $A[i]$=$10^8$ , $9*10^8$
-----Sample Input:-----
2
3
100000000 900000000 100000000
1
900000000
-----Sample Output:-----
2
0
# cook your dish here
def subCount(arr, n, k=10): 
 
    mod =[] 
    for i in range(k + 1): 
        mod.append(0) 
    cumSum = 0
    for i in range(n): 
        cumSum = cumSum + arr[i] 

        mod[((cumSum % k)+k)% k]= mod[((cumSum % k)+k)% k] + 1
      
    
    result = 0  # Initialize result 
       
    # Traverse mod[] 
    for i in range(k): 
        if (mod[i] > 1): 
            result = result + (mod[i]*(mod[i]-1))//2

    result = result + mod[0] 
       
    return result 
    
for t_itr in range(0,int(input())):
    n = int(input())
    a = list(map(str, input().split()))
    b = []
    for i in a:
        b.append(int(i[0]))
    res = subCount(b, n, 10)
    print(res)
    
    

# cook your dish here
def subCount(arr, n, k=10): 
 
    mod =[] 
    for i in range(k + 1): 
        mod.append(0) 
    cumSum = 0
    for i in range(n): 
        cumSum = cumSum + arr[i] 

        mod[((cumSum % k)+k)% k]= mod[((cumSum % k)+k)% k] + 1
      
    
    result = 0  # Initialize result 
       
    # Traverse mod[] 
    for i in range(k): 
        if (mod[i] > 1): 
            result = result + (mod[i]*(mod[i]-1))//2

    result = result + mod[0] 
       
    return result 
    
for t_itr in range(0,int(input())):
    n = int(input())
    a = list(map(str, input().split()))
    b = []
    for i in a:
        b.append(int(i[0]))
    res = subCount(b, n, 10)
    print(res)
    
    
