Even and Odd#13071

Even and Odd

1.5 seconds
256 megabytes

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

A = a_0 + 10 \cdot a_1 + 10^2 \cdot a_2 + \ldots + 10^{m-1} \cdot a_{m-1}.

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

S_{\mathrm{odd}}(A) - P_{\mathrm{odd}}(A) = S_{\mathrm{even}}(A) - P_{\mathrm{even}}(A).

Here:

For example, for A = 1234 we have a_0 = 4, a_1 = 3, a_2 = 2, a_3 = 1. Then:

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:

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.

Input

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 .

Output

For each query, output the required number on a separate line in full, without leading zeros.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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.