Friend Number

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 <= 101000). 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

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐