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: UNKNOWN_DIFFICULTY

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))


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))


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))


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))


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))


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))
	if n < 5 and len(s) > 1:
		print(9 - n)
	else:
		if rem >= 5:
			rem = 9 - rem
		print(rem)


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))


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)


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)
		elif 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))