Hardik likes the number 9, One of his friend gave him a number N, and want him to turn it into a multiple of 9. His friend gave him some restriction that 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. So Hardik has to find the minimum amount of time (in seconds) needed to accomplish this.

CONSTRAINT

• 1≤T≤1000
• 1≤N≤10^(10^5)
• N will not contain leading zeroes.