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

Difficulty: interview

Starter code:

Solutions:
def subCount(arr, n, k):

    mod = []
    for i in range(k + 1):
        mod.append(0)


    cumSum = 0
    for i in range(n):
        cumSum = cumSum + arr[i]

        # as the sum can be negative,
        # taking modulo twice
        mod[((cumSum % k) + k) % k] = mod[((cumSum % k) + k) % k] + 1

    result = 0  # Initialize result

    for i in range(k):


        if (mod[i] > 1):
            result = result + (mod[i] * (mod[i] - 1)) // 2


    result = result + mod[0]

    return result
t=int(input())
while t:
    t=t-1
    n=int(input())
    a=list(map(int,input().split()))
    for i in range(n):
        if a[i]==100000000:
            a[i]=1
        elif a[i]==900000000:
            a[i]=9
    s=10

    print(subCount(a,n,s))


def subCount(arr, n, k): 
    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 
    for i in range(k): 
        if (mod[i] > 1): 
            result = result + (mod[i]*(mod[i]-1))//2
    result = result + mod[0] 
    return result 
def inp(x):
    return int(x.rstrip('0'))
def main(t):
    k = 10
    n = int(input())  
    arr =  list(map(inp,input().split()))
    print(subCount(arr, n, k))   
    if t>1:
        main(t-1)
main(int(input()))

def subCount(arr, n, k): 
    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 
    for i in range(k): 
        if (mod[i] > 1): 
            result = result + (mod[i]*(mod[i]-1))//2
    result = result + mod[0] 
    return result 
def inp(x):
    return int(x.rstrip('0'))
def main(t):
    k = 10
    n = int(input())  
    arr =  list(map(inp,input().split()))
    print(subCount(arr, n, k))   
    if t>1:
        main(t-1)
main(int(input())) 


import atexit
import io
import sys
import math
from collections import defaultdict,Counter

# _INPUT_LINES = sys.stdin.read().splitlines()
# input = iter(_INPUT_LINES).__next__
# _OUTPUT_BUFFER = io.StringIO()
# sys.stdout = _OUTPUT_BUFFER

# @atexit.register
# def write():
#     sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

# sys.stdout=open("CP2/output.txt",'w')
# sys.stdin=open("CP2/input.txt",'r')

m=pow(10,9)
t=int(input())
for i in range(t):
    n=int(input())
    d={0:1}
    a=list(map(int,input().split()))
    s=0
    ans=0
    for j in a:
        s+=j
        need=s%m
        ans+=d.get(need,0)
        s1=d.setdefault(s%m,0)
        d[s%m]+=1
    print(ans)

# -*- coding: utf-8 -*-
"""
Created on Wed Jun 24 21:34:16 2020

@author: PREET MODH
"""

def subCount(arr, n, k): 
    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
    for i in range(k): 
        if (mod[i] > 1): 
            result = result + (mod[i]*(mod[i]-1))//2
    
    result = result + mod[0] 
    return result 

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    for i in range(len(a)):
        a[i]=a[i]//10**8
  
    print(subCount(a, n, 10))

from sys import stdin, stdout
M=10**8
for _ in range(int(stdin.readline())):
    n = int(stdin.readline())
    a=list([int(x)//M for x in stdin.readline().split()])
    d={0:1};s=ans=0
    for v in a:
        s+=v
        req=s%10
        ans+=d.get(req,0)
        d[req]=d.get(req,0)+1
    print(ans)



def solve(n, l):
    k = 10
    d =[] 
    for i in range(k + 1): 
        d.append(0) 
    cumSum = 0
    for i in range(n): 
        cumSum = cumSum + l[i] 
        d[((cumSum % k)+k)% k]= d[((cumSum % k)+k)% k] + 1
    result = 0 
    for i in range(k):  
        if (d[i] > 1): 
            result = result + (d[i]*(d[i]-1))//2
    result = result + d[0] 
       
    return result  

t = int(input())
for i in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    for i in range(n):
        l[i]=int(l[i]/100000000)
    print(solve(n, l)) 

from collections import defaultdict
import collections
def subarraysDivByK(A,K):
        d = collections.defaultdict(int)
        # generate accum
        accum = [0,]*len(A)
        for ai, a in enumerate(A): 
            div = a%K if ai == 0 else (a+accum[ai-1])%K
            accum[ai] = div; d[div] += 1 
        # count
        #print(accum,d)
        ans = 0
        for k,v in list(d.items()):
            ans +=  v*(v-1)//2
            if k == 0: ans += v 
        return ans
t=int(input())
for i in range(0,t):
      n=int(input())
      arr =  [int(x) for x in input().split()]   
      Sum = 1000000000
      print(subarraysDivByK(arr,Sum))  

  


from sys import stdin, stdout
M=10**8
for _ in range(int(stdin.readline())):
    n = int(stdin.readline())
    a=list(map(lambda x:int(x)//M, stdin.readline().split()))
    d={0:1};s=ans=0
    for v in a:
        s+=v
        req=s%10
        ans+=d.get(req,0)
        d[req]=d.get(req,0)+1
    print(ans)

from collections import defaultdict
from itertools import accumulate
for _ in range(int(input())):
        n=int(input())
        A=list(map(int,input().split()))
        K=10**9
        ans,rems=0,{0:1}
        for i in range(len(A)):
            if i>0: A[i]+=A[i-1]
            rem=A[i]%K
            if rem in rems:
                ans+=rems[rem]
                rems[rem]+=1
            else:
                rems[rem]=1
        print(ans)


for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    pref = []
    # mods = []
    d = {}
    ans = 0
    for i in range(n):
        if i ==0:
            pref.append(a[0])
        else:
            pref.append((pref[-1]+a[i]))
        b = pref[-1]%1000000000
        if b in d.keys():
            if b==0:
                ans +=1
            ans +=d[b]
            d[b]+=1
        else:
            if b==0:
                ans +=1
            d[b] = 1
    print(ans)

# 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
for _ in range(int(input())):
    N = int(input())
    seq = list(map(int,input().split()))
    count = {0:1}
    total = 0
    summ = 0
    for i in range(N):
        summ += seq[i]
        r = summ%(10**9)
        if count.get(r,0):
            total += count[r]
            count[r]+=1
        else:
            count[r] = 1
    print(total)


import collections
def subarraysDivByK(A, K):
    P = [0]
    for x in A:
        P.append((P[-1] + x) % K)

    count = collections.Counter(P)
    return sum(v*(v-1)/2 for v in count.values())
    
t=int(input())
for _ in range(t):
    n=int(input())
    arr=map(int,input().split())
    print(int(subarraysDivByK(arr,1000000000)))

t=int(input())
def subCount(arr, n, k): 
    #print(arr)
    mod =[] 
    for i in range(k + 1): 
        mod.append(0) 
    allSum = 0
    for i in range(n): 
        allSum = allSum + arr[i] 
        #print(allSum)
        mod[(allSum % k)] += 1
        #print(mod)
      
    
    res = 0 
    for i in range(k): 
        if (mod[i] > 1): 
            res = res + (mod[i]*(mod[i]-1))//2
            
    res = res + mod[0] 
       
    return res
for _ in range(t):
    n=int(input())
    a=[int(k)//(10**8) for k in input().split()]
    #print(a)
    print(subCount(a,n,10))


# 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]))
    result = subCount(b, n, 10)
    print(result)
    
    



def subCount(arr, n, k): 
	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 
	
t=int(input())
while(t):
    n=int(input())
    a=list(map(int,input().split()))
    b=[]
    for i in a:
        b.append(i//100000000)
    
    print(subCount(b, n, 10)) 
    t=t-1

def subCount(arr, n, k): 
    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

    for i in range(k): 

        if (mod[i] > 1): 
            result = result + (mod[i]*(mod[i]-1))//2
    result = result + mod[0] 
    return result 



for _ in range(int(input())):
    n = int(input())
    ar = [int(i) for i in input().split()]
    a = []
    for i in ar:
        if i==100000000:
            a.append(1)
        else:
            a.append(9)
    print(subCount(a, n, 10))

def subCount(arr, n, k, mod, cumSum, result): 
	for i in range(k + 1):mod.append(0) 	
	for i in range(n):cumSum += arr[i];mod[((cumSum % k)+k)% k]= mod[((cumSum % k)+k)% k] + 1
	for i in range(k): 
		if (mod[i] > 1):result = result + (mod[i]*(mod[i]-1))//2	
	return result + mod[0]
for _ in range(int(input())):
    n,a = int(input()),list(map(int,input().split()))
    for i in range(n):a[i] //= (10**8)
    print(subCount(a,n,10,[],0,0))


# code from gfg: https://www.geeksforgeeks.org/count-sub-arrays-sum-divisible-k/
while(1):
    for _ in range(int(input())):
        n=int(input())
        l=list(map(int,input().split()))
        g=[]
        for i in l:
            if i==900000000:
                g.append(9)
            else:
                g.append(1)
        k=10
        m = []
        for i in range(k + 1):
            m.append(0)
        cs = 0
        for i in range(n):
            cs = cs + g[i]
            m[((cs % k) + k) % k] = m[((cs % k) + k) % k] + 1
        r = 0
        for i in range(k):
            if (m[i] > 1):
                r = r + (m[i] * (m[i] - 1)) // 2
        r = r + m[0]

        print(r)
    break



# 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]))
    result = subCount(b, n, 10)
    print(result)
    


# 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]))
    result = subCount(b, n, 10)
    print(result)
    
    


# 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]))
    result = subCount(b, n, 10)
    print(result)
    
    


for s in[*open(0)][2::2]:
 d = {0: 1}
 t = 0
 for x in s.split():
  t = (t + int(x[0])) % 10
  d[t] = d.get(t, 0) + 1
 print(sum(k * (k - 1) // 2 for k in list(d.values())))


# cook your dish here
def subCount(arr, n, k):
  
    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  

   
    for i in range(k):

        if (mod[i] > 1):
            result = result + (mod[i] * (mod[i] - 1)) // 2

    result = result + mod[0]

    return result
for _ in range(int(input())):
    n=int(input())
    a=input().split()
    b=[]
    for i in range(len(a)):
        b.append(int(a[i][0]))
    print(subCount(b,len(b),10))