問題文

正整数 N に対して、f(N) を以下で定めます。

• N の各桁の数字を並び替えて得られる整数の集合を S とする。ただし、並び替えた結果先頭に 0 が続く場合 leading zero として解釈する。例えば、N=102 のとき S=\lbrace 12,21,102,120,201,210\rbrace である。S の要素全てを割り切る最大の整数を f(N) とする。

10^{18} 以下の正整数 K が与えられます。 f(N)=K を満たすような 10^{18} 以下の正整数 N が存在するか判定し、存在する場合 1 つ求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力は全て整数
• 1 \leq T \leq 10^4
• 1 \leq K \leq 10^{18}

入力例 1

2
3
10

出力例 1

123
-1

1 番目のテストケースについて、N=123 のとき S=\lbrace{123,132,213,231,312,321\rbrace} であり S の全ての要素を割り切る最大の整数は 3 です。したがって f(N)=3 であり、この出力は条件を満たします。

2 番目のテストケースについて、f(N)=10 を満たす 10^{18} 以下の正整数 N が存在しないことが証明できます。