Friend Number II

Time Limit: 1 Second
Memory Limit: 32768 KB

Given a positive integer *x*, let S(x) denotes the sum of all *x*'s digits. Two integers *x* and *y* are friend numbers if S(x)=S(y).
Here comes the problem: Given a positive integer *x*, of course it has a lot of friend numbers, find the smallest one which is greater than *x*,please.

**Input**

There are multiple test cases. The first line of input is an integer *T* (0<*T*<230) indicating the number of test cases.
Then *T* test cases follow. Each case is an integer *x* (0<*x*<=10^{1000}).

**Output**

For each test case, output the result integer in a single line.

**Sample Input**

3
12
19
222

**Sample Output**

21
28
231

*
Note: No input data start with digit 0 and you should not output a number starts with 0.
*

Submit
Status