Do you think that being eccentric is easy? This is not the case when you're a number.
The degree of eccentricity of a 2N-digit integer X (possibly with leading zeroes) is defined as the smallest possible value of |a + b - 10^N| for some N-digit integers a and b (again, possibly with leading zeroes) such that S_d(X) = S_d(a) +S_d(b) holds for every digit d, where S_d(P) (0 ≤ d ≤ 9) is the number of occurrences of digit d in the decimal representation of P. For example, the degree of eccentricity of amusing numbers (see problem Counting Amusing Numbers) is equal to 0, while the degree of eccentricity of 192747 equals to 7 (|274 + 719 - 1000| = 7).
You are given a bunch of numbers of even lengths. Find the degree of eccentricity of each of them.
The first line contains the number of test cases T (1 ≤ T ≤ 1000). Each of the next T lines contains an integer number of an even length (possibly with leading zeroes). The total length of all numbers (except T) doesn't exceed 10^6.
For each test case print one line containing the degree of eccentricity of the corresponding number.