Chef lives in a big apartment in Chefland. The apartment charges maintenance fees that he is supposed to pay monthly on time. But Chef is a lazy person and sometimes misses the deadlines. The apartment charges 1000 Rs per month as maintenance fees. Also, they also charge a one-time fine of 100 Rs for each of the late payments. It does not matter how late the payment is done, the fine is fixed to be Rs.100.
Chef has been living in the apartment for N months. Now, he wants to switch the apartment, so he has to pay the entire dues to the apartment. The deadline for the N-th month is also over. From his bank statement, he finds the information whether he paid apartment rent for a particular month for not. You are given this information by an array A of size N, where Ai (can be either 0 or 1) specifies whether he has paid the 1000Rs in the i-th month or not. Assume that Chef paid the fees in the i-th month, then this fees will be considered for the earliest month for which Chef has not yet paid the fees.

For example, assume Chef did not pay any money in first month and 1000Rs in the second month. Then this rent of 1000Rs will be considered for 1st month. But this counts as late payment for the first month's fees, and hence he will have to pay Rs. 100 for that. And since the payment he made in the second month is not accounted for the second month, but rather for the first month, he will incur a fine of Rs.100 even for the second month. 

He has not paid any of the fines so far. Can you please help in finding Chef total due (all the fines, plus all the unpaid maintenance fees) that he has to pay to apartment? 

-----Input-----
First line of the input contains an integer T denoting number of test cases. The description of T test cases follows.
The first line of each test cases contains an integer N denoting the number of months for which you have to calculate the total amount of money that Chef has to pay at the end of the n month to clear all of his dues.
Next line of each test case contains N space separated integers (each of them can be either 0 or 1) denoting whether Chef paid the 1000Rs fees in the corresponding month or not. If the corresponding integer is 1, it means that Chef paid the maintenance fees for that month, whereas 0 will mean that Chef did not pay the maintenance fees that month.

-----Output-----
For each test case, output a single integer denoting the total amount including fine that Chef has to pay.

-----Constraints-----Constraints
- 1 ≤ T ≤ 25
- 0 ≤ Ai ≤ 1

-----Subtasks-----
Subtask #1 (30 points)
- 1 ≤ N ≤ 103

Subtask #2 (70 points)
- 1 ≤ N ≤ 105

-----Example-----
Input
4
2
1 1
2
0 0
3
0 1 0
2
0 1

Output
0
2200
2300
1200

-----Explanation-----
Example case 1. Chef paid maintenance fees for both the months. So, he does not have any dues left.
Example case 2. Chef did not pay the maintenance fees for any of the months. For the first month, he has to pay 1000Rs, and 100Rs fine as a late payment. For second month payments, he just have to pay 1100Rs. So, in total he has a due of 1100 + 1100 = 2200 Rs.
Example case 3. In the first month, Chef did not pay his maintenance fees. He paid the maintenance of first in the second month. So, he paid a fine of 100Rs for first month. For second and third month, Chef did not pay the maintenance fees. So, he has to pay 1000Rs + 100Rs (of fine) for second month and only 1000Rs + 100Rs (of fine) for third month. In total, Chef has got to pay 100 + 1100 + 1100 = 2300 Rs. 
Example case 4. In the first month, Chef did not pay his maintenance fees. He paid the maintenance of first in the second month. So, he paid a fine of 100Rs for first month. For second month, Chef did not pay the maintenance fees. So, he has to pay 1000Rs + 100Rs (of fine) for second month. In total, Chef has got to pay 100 + 1100 = 1200 Rs.

Difficulty: interview

Starter code:

Solutions:
for i in range(int(input())):
    a=int(input())
    b=input().split()
    if '0' in b:
        print(100*(a-b.index('0'))+b.count('0')*1000)
    else:
        print(0)


for i in range(int(input())):
  x=int(input())
  y=input().split()
  if '0' in y:
    print(100*(x-y.index('0'))+y.count('0')*1000)
  else:
    print(0)  

# cook your dish here
for t in range(int(input())):
    total=0
    n=int(input())
    a=list(map(int,input().split()))
    
    for i in range(0,n):
        
        if a[i]==0:
            total=total+1100
        else:
            if total>=1100:
                
                total=total-1000
                total=total+1100
    print(total)
        
    
    
    

for i in range(int(input())):
  x=int(input())
  y=input().split()
  if '0' in y:
    print(100*(x-y.index('0'))+y.count('0')*1000)
  else:
    print(0)  



for _ in range(int(input())):
    n=int(input())
    s=list(map(int,input().split()))
    total=0
    for i in range(0,n):
        if s[i]==0:
            total+=1100
        else:
            if total>=1100:
                total-=1000
                total+=1100
    print(total)

# cook your dish here
for _ in range(int(input())):
    N=int(input())
    inp_arr=tuple(int(i) for i in input().strip().split())
    fine=0
    maxMaint=1000*N
    for i in range(N):
        if(inp_arr[i]==0):
            if(fine==0):
                fine=100*(N-i)
        else:
            maxMaint-=1000
            
    print(maxMaint+fine)
            


T=int(input())
for i in range(T):
    N=int(input())
    A=[int(i) for i in input().split()]
    m=0
    for i in range(N):
        if A[i]==0:
            m=m+1000
    for i in range(N):
        if A[i]==0:
            k=len(A)-i
            break
        else:
            k=0
    n=m+k*100
    print(n)
        
        
    


T=int(input())
for i in range(T):
    N=int(input())
    A=[int(i) for i in input().split()]
    m=0
    for i in range(N):
        if A[i]==0:
            m=m+1000
        for i in range(N):
            if A[i]==0:
                k=len(A)-i
                break
            else:
                k=0
    n=m+k*100
    print(n)
        
        
    


for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    c=0
    if l.count(1)==n:
        print(0)
    else:    
        print(l.count(0)*1000+(n-l.index(0))*100)
            
            

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    c=0
    if l.count(1)==n:
        print(0)
    else:    
        for i in range(n):
            if l[i]==0:
               c+=1000
        print(c+(n-l.index(0))*100)
            
            

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    c=0
    if l.count(1)==n:
        print(0)
    else:    
        for i in range(n):
            if l[i]==0:
                c+=(n-i)*100
                break
        t=c+l.count(0)*1000    
        print(t)
            
            

for _ in range(int(input())):
    n = int(input())
    statement = list(map(int, input().split()))
    fine = 0
    for i, v in enumerate(statement):
        if v == 0:
            fine = (n-i)*100    
            break
                
    total = fine + 1000*statement.count(0)
    print(total)
            

# cook your dish here
try:
    for _ in range(int(input())):
        N = int(input())
        Log = input().split()
        if '0' in Log:
            print((100*(N-Log.index('0')))+Log.count('0')*1000)
        else:
            print(Log.count('0')*1000)
except:
    pass

# cook your dish here
t=int(input())
for i in range(t):
    n=int(input())
    l1=list(map(int,input().split()))
    c=0
    flag=0
    for i in range(n):
        if(l1[i]==0):
            c+=1100
            flag=1
        elif(l1[i]==1):
            if(flag==1):
                c+=100
    print(c)

# cook your dish here
for _ in range(int(input())):
    n = int(input())
    l = list(map(int,input().split()))
    c = 0
    flg = 0
    for i in range(n):
        if l[i]==0:
            c+=1100
            flg=1
        elif l[i]==1:
            if flg==1:
                c+=100
    print(c)

# cook your dish here
for _ in range(int(input())):
    n = int(input())
    arr = input().split()
    i = 0
    while i != n and arr[i] != '0':
        i += 1
    sum = 0
    for j in range(i,n):
        if arr[j] == '0':
            sum += 1100
        else:
            sum += 100
    print(sum)



for _ in range(int(input())):
    N = int(input())
    L = list(map(int, input().split()))
    
    late = False
    lN = 0
    for i in L:
        if i == 0: late = True
        if late: lN += 1 
    
    print(L.count(0)*1000 + lN*100)

# cook your dish here
for h in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=0
    if l.count(1)==n:
        print(0)
    else:
        for i in l:
            if i==0:
                s+=1100 
            elif s!=0:
                s+=100 
        print(s)

t=int(input())
for i in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    if len(set(l))==1 and l[0]==1:
        print(0)
    elif len(set(l))==1 and l[0]==0:
        print(n*1100)
    else:
        f=1
        c=0
        for j in range(n):
            if l[j]==1 and f==0:
                c=c+100
            elif l[j]==0:
                c=c+1100
                f=0
        print(c)

# cook your dish here
try:
    for T in range(int(input())):
        N = int(input())
        Log = input().split()
        if '0' in Log:
            print((100*(N-Log.index('0')))+Log.count('0')*1000)
        else:
            print(Log.count('0')*1000)
except:
    pass