#1615 RepresentableNumbers

14  20 s   128 MB

Description

Let's call a positive integer A totally odd if each digit in its decimal notation is odd, i.e., one of 1, 3, 5, 7, 9. For example, integers 9, 513, 77777 are totally odd and integers 2 and 99990 are not.

A positive integer N is called representable if it can be represented as N = A + B, where both A and B are totally odd numbers. For example, 2 = 1 + 1 and 4752 = 1377 + 3375 are representable, while 3 and 220 are not.

Given an int X, print the smallest representable number that is greater than or equal to X.

Input

The first line of the input gives the number of test cases, T (1 <= T <= 200).

For each test case, one positive integer x, which is between 1 and 100,000,000, inclusive, will be given in one line.

Output

For each test case, print the smallest representable number as explained in the problem statement, in one line.

Sample Output

5
1
999
2000
4201234
10101010
2
1000
2000
4222222
10102222