AT_utpc2022_a Shuffle and GCD

正整数 $ 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 $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ K $

$ T $ 行出力せよ。 $ i\ (1\leq i \leq T) $ 行目には $ i $ 番目のテストケースについて、 $ f(N)=K $ となる条件を満たす $ N $ が存在する場合そのような $ N $ を一つ出力し、存在しない場合 $ -1 $ を出力せよ。解が複数存在する場合、どれを出力しても正解とみなされる。

### Sample Explanation 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 $ が存在しないことが証明できます。 ### Constraints - 入力は全て整数 - $ 1 \leq T \leq 10^4 $ - $ 1 \leq K \leq 10^{18} $