Divisibility by 9

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
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 ≤ 10^{5}
 1 ≤ N ≤ 10^{105}
 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.
Author:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/DIVNINE 
Tags  kevinsogo, snck15el 
Date Added:  3062015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 