eolymp
bolt
Try our new interface for solving problems
Problems

Degree Of Number`s Eccentricity

Degree Of Number`s Eccentricity

Time limit 2 seconds
Memory limit 256 MiB

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) (0d9) 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.

Input data

The first line contains the number of test cases T (1T1000). 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.

Output data

For each test case print one line containing the degree of eccentricity of the corresponding number.

Examples

Input example #1
3
9820
192747
000001
Output example #1
0
7
900
Author Gennady Korotkevich
Source Gennady Korotkevich Contest 1, Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013