Let be a natural number, and let a_{m-1} a_{m-2} \ldots a_1 a_0 be its decimal representation without leading zeros, that is
In other words, the digits are numbered from right to left, starting at zero: a_0 is the last digit (the units digit), a_1 is the tens digit, and so on. The number is called the position of the digit a_i.
The number is called balanced if
Here:
S_{\mathrm{odd}}(A) is the sum of all digits a_i that are odd numbers;
S_{\mathrm{even}}(A) is the sum of all digits a_i that are even numbers;
P_{\mathrm{odd}}(A) is the sum of all digits a_i standing at odd positions ;
P_{\mathrm{even}}(A) is the sum of all digits a_i standing at even positions .
For example, for A = 1234 we have a_0 = 4, a_1 = 3, a_2 = 2, a_3 = 1. Then:
S_{\mathrm{odd}} = 1 + 3 = 4;
S_{\mathrm{even}} = 2 + 4 = 6;
P_{\mathrm{odd}} = 3 + 1 = 4;
P_{\mathrm{even}} = 4 + 2 = 6.
Since S_{\mathrm{odd}} - P_{\mathrm{odd}} = 4 - 4 = 0 and S_{\mathrm{even}} - P_{\mathrm{even}} = 6 - 6 = 0 hold, the number is balanced.
However, for A = 12340 the positions of all the original digits are increased by one: a_0 = 0, a_1 = 4, a_2 = 3, a_3 = 2, a_4 = 1. Now:
S_{\mathrm{odd}} = 4;
S_{\mathrm{even}} = 6;
P_{\mathrm{odd}} = 4 + 2 = 6;
P_{\mathrm{even}} = 0 + 3 + 1 = 4.
Since 4 - 6 \ne 6 - 4, the number is not balanced.
You are given queries. In each query, a natural number is given. Find the smallest balanced number whose decimal representation begins with the decimal representation of the number . In other words, is obtained by appending k \ge 0 more digits to the right of (any digits, including zeros); the case k = 0, that is M = N, is allowed. It can be proven that such a number always exists.
The first line contains a single integer (1 \le Q \le 10^6) — the number of queries.
Each of the following lines contains a single natural number , written without leading zeros. It is guaranteed that 1 \le |N| \le 10^6 and the sum of over all queries does not exceed 10^6, where is the number of digits of the number .
For each query, output the required number on a separate line in full, without leading zeros.
Example 1
Example 2
In the first example:
is itself balanced (see above), so M = N.
is not balanced: S_{\mathrm{odd}} - P_{\mathrm{odd}} = 9 - 0 = 9, while S_{\mathrm{even}} - P_{\mathrm{even}} = 0 - 9 = -9. The next candidates are 90, 91, \ldots, 99; among them is balanced.
For the answer is : here a_0 = 1, a_1 = 8, a_2 = 0, a_3 = 2, a_4 = 9, a_5 = 9, so S_{\mathrm{odd}} - P_{\mathrm{odd}} = (1 + 9 + 9) - (8 + 2 + 9) = 0 and S_{\mathrm{even}} - P_{\mathrm{even}} = (8 + 0 + 2) - (1 + 0 + 9) = 0. No smaller number fits.