Friend Number

Time Limit: 1 Second
Memory Limit: 32768 KB

Given a positive integer *x*, let P(*x*) denotes the product of all *x*'s digits. Two integers *x* and *y* are friend numbers if P(*x*) = P(*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*.

**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}). You may assume that *x* has no leading zero.

**Output**

For each test case, output the result integer in a single line. You should not output a number with leading zero.

**Sample Input**

3
12
19
222

**Sample Output**

21
33
241

Author:

**CAO, Peng**
Source:

**The 7th Zhejiang Provincial Collegiate Programming Contest**
Submit
Status