Chef Zidane likes the number 9. He has a number N, and he wants to turn it into a multiple of 9. He cannot add or remove digits, and he can only change one digit at a time. The only allowed operation is to increment or decrement a digit by one, and doing this takes exactly one second. Note that he cannot increase a digit 9 or decrease a digit 0, and the resulting number must not contain any leading zeroes unless N has a single digit.

Chef Zidane wants to know the minimum amount of time (in seconds) needed to accomplish this. Please help him, before his kitchen gets overwhelmed with mist!

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of one line containing a single positive integer N.

-----Output-----
For each test case, output a single line containing the answer.

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 10105
- N will not contain leading zeroes.
- Each test file is at most 3Mb in size.

-----Example-----
Input:4
1989
86236
90210
99999999999999999999999999999999999999988

Output:0
2
3
2

-----Explanation-----
Example case 1. 1989 is already divisible by 9, so no operations are needed to be performed.
Example case 2. 86236 can be turned into a multiple of 9 by incrementing the first and third digit (from the left), to get 96336. This takes 2 seconds.
Example case 3. 90210 can be turned into a multiple of 9 by decrementing the third digit twice and the fourth digit once, to get 90000. This takes 3 seconds.

Difficulty: interview

Starter code:

Solutions:
s=int(input())
while(s>0):
 s-=1
 a=input()
 c=0
 for x in a:
  c+=int(x)
 if(c<9 and len(a)!=1):
  print(9-c%9)
 else:
  print(min(9-c%9,c%9))


s=int(input())
while(s>0):
 s-=1
 a=input()
 c=0
 for x in a:
  c+=int(x)
 if(c<9 and len(a)!=1):
  print(9-c%9)
 else:
  print(min(9-c%9,c%9))


# cook your dish here
test=int(input())
for _ in range(test):
  n=input()
  s=0
  for i in n:
   s+=int(i)
  if len(n)>1 and s<9:
   print(9-(s%9))
  else:
   print(min(s%9,9-s%9))


# cook your dish here

# def getSum(n): 
#     sum = 0
#     while (n != 0): 
#         sum = sum + int(n % 10) 
#         n = int(n/10) 
#     return sum
 

for _ in range(int(input())):
 n = input()
 s=0
 for i in n:
  s+=int(i)
 if s<9 and len(n)!=1:
  print(9-s%9)
 else:
  print(min(9-s%9,s%9))

# cook your dish here
t=int(input())
while t:
  t-=1
  n=input()
  s=0
  for i in n:
   s+=int(i)
  if len(n)>1 and s<9:
   print(9-(s%9))
  else:
   print(min(s%9,9-s%9))


'''
author:"Pradhyumna Singh Rathore"
'''
for _ in range(int(input())):
 n=input()
 ans=sum(list(map(int,n)))
 if(len(n)>1 and ans<9):
  print(9-ans)
 else:
  print(min(ans%9,9-ans%9))


# cook your dish here
try:
 for _ in range(int(input())):
  n=input()
  ans=sum(list(map(int,n)))
  if(len(n)>1 and ans<9):
   print(9-ans)
  else:
   print(min(ans%9,9-ans%9))
except:
 pass


for _ in range(int(input())):
 n=input()
 ans=sum(list(map(int,n)))
 if(len(n)>1 and ans<9):
  print(9-ans)
 else:
  print(min(ans%9,9-ans%9))

for i in range(int(input())):
 n=input()
 total=sum(list(map(int,n)))
 if len(n)>1 and total<9:
  print(9-total)
 else:
  print(min(total%9,9-total%9))

for _ in range(int(input())):
 a=input()
 res=sum(map(int,a))
 if len(a)>1 and res<9:
  print(9-res)
 else:
  print(min(9-res%9,res%9))


# cook your dish here
for j in range(int(input())):
 n=input()
 c=sum(map(int,n))
 if(len(n)>1 and c<9):
  print(9-c)
 else:
  print(min(c%9,9-c%9))

# cook your dish here
for j in range(int(input())):
 n=input()
 c=sum(map(int,n))
 if(len(n)>1 and c<9):
  print(9-c)
 else:
  print(min(c%9,9-c%9))

for j in range(int(input())):
 n=input()
 c=sum(map(int,n))
 if(len(n)>1 and c<9):
  print(9-c)
 else:
  print(min(c%9,9-c%9))

for j in range(int(input())):
 n=input()
 c=sum(map(int,n))
 if(len(n)>1 and c<5):
  print(9-c)
 else:
  print(min(c%9,9-c%9))

t=int(input())
for _ in range(t):
 n=input()
 y=[int(x) for x in n]
 z=sum(y)
 if z<5 and len(y)>1:
  print(9-z)
 else:
  print(min(z%9, 9-z%9))

for i in range(int(input())):
 s=input()
 rem=int(s)%9
 n=sum(map(int,s))
 #print(rem,n)
 if n<5 and len(s)>1:
  print(9-n)
 else:
  if rem >= 5:
   rem=9-rem
  print(rem)

for _ in range(int(input())):
 s=input()
 rem=int(s)%9
 n=sum(map(int,s))
 if n<5 and len(s)>1:
  print(9-n)
 else:
  if rem >= 5:
   rem=9-rem
  print(rem)

for _ in range(int(input())):
 s=input()
 rem=int(s)%9
 n=sum(map(int,s))
 if n<5 and len(s)>1:
  print(9-n)
 else:
  if rem >= 5:
   rem=9-rem
  print(rem)

# cook your dish here
for u in range(int(input())):
 n=input()
 s=sum(map(int,n))
 if(len(n)>1 and s<5):
  print(9-s)
 else:
  print(min(s%9,9-s%9))

'''

This File is created by Saurabh Sisodia
email address... "ssisodia507@gmail.com"

................................................................................    ............

'''
for _ in range(int(input())):
 n=input()
 sum=0
 len=0
 for v in n:
  len+=1
  sum+=int(v)
 rem=sum%9
 if len>1 and sum<9:
  ans=9-rem
 else:
  ans=min(rem,9-rem)
 print(ans)

# cook your dish here
t=int(input())
for loop in range(t):
 n=input()
 sum=0
 addable=0
 for i in n:
  sum+=ord(i)-ord('0')
  addable+=ord('9')-ord(i)
 rem=sum%9
 if(int(n)>9):
  
  if(rem>9-rem):
   if(9-rem<=addable):
    print(9-rem)
   else:
    print(rem)
  else:
   if(sum>rem):
    print(rem)
   else:
    print(9-rem)
 else:
  print(min(rem,9-rem))

t=int(input())
for _ in range(t):
 s=input()
 l=[int(x) for x in s]
 ss=sum(l)
 if ss<5 and len(l)>1:
  print(9-ss)
 else:
  print(min(ss%9, 9-ss%9))



for _ in range(int(input())):
 li=[int(i) for i in list(input())]
 if len(li)!=1 and sum(li)<9:print(9-(sum(li)%9))
 else:print(min(sum(li)%9,9-(sum(li)%9)))