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