AT_utpc2022_a.Shuffle and GCD

对于正整数 $N$，定义 $f(N)$ 如下：

• 令 $S$ 为将 $N$ 的各位数字重新排列所能得到的所有整数的集合。注意，如果重新排列后数字开头出现 $0$，应视作前导零。比如，当 $N=102$ 时，$S=\lbrace 12,21,102,120,201,210\rbrace$。$f(N)$ 定义为能整除 $S$ 中所有元素的最大整数。

给定一个不超过 $10^{18}$ 的正整数 $K$。判断是否存在一个不超过 $10^{18}$ 的正整数 $N$，满足 $f(N)=K$。如果存在，输出其中一个满足条件的 $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$。

样例解释 1

对于第 $1$ 个测试用例，当 $N=123$ 时，$S=\lbrace123,132,213,231,312,321\rbrace$，这些数的最大公约数为 $3$，所以 $f(N)=3$，因此这个输出是正确的。

对于第 $2$ 个测试用例，能够证明不存在 $N$ 满足 $f(N)=10$。

数据范围

• 所有输入均为整数
• $1 \leq T \leq 10^4$
• $1 \leq K \leq 10^{18}$

由 ChatGPT 5 翻译