Concat Coprimes

問題文

正整数 $x, y$ に対して $f(x, y)$ を以下のように定義します。

• 十進表記の $x, y$ をそれぞれ文字列として解釈して得られる文字列を $z$ とする。 $z$ を十進表記の整数として解釈したときの値を $f(x, y)$ とする。

例えば $f(3, 14) = 314, ~ f(100, 3) = 1003$ です。

正整数 $N$ が与えられます。 以下の条件をすべて満たす正整数 $X$ が存在するか判定してください。
また、存在する場合はこのうちあり得る最小値を求めてください。

• $X$ は $N$ の倍数である
• $N$ と互いに素な $2$ つの正整数 $a, b$ を用いて $X = f(a, b)$ と表すことができる

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

制約

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 10^9$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

各テストケースは以下の形式で与えられる。

出力

条件をすべて満たす正整数 $X$ が存在するならば $X$ を、存在しないならば -1 を出力せよ。

サンプル

入力例

2
7
100

出力例

14
-1

$1$ 番目のテストケースについて、 $X = 14$ は条件を満たします。

• $14$ は $7$ の倍数である
• $a = 1,~ b = 4$ はどちらも $7$ と互いに素である

$2$ 番目のテストケースについて、 条件を満たす $X$ は存在しません。