对于任意正整数 $y$，我们定义 $A(y)$ 为所有与 $y$ 的数字组成相同的正整数集合。形式化地，我们考虑 $y$ 在十进制表示下的所有数字序列（不含前导零），然后对该序列进行所有可能的排列。对于每一种排列，我们去掉前导零并将剩余数字重新组合成一个整数。所有通过这种方式得到的整数都属于 $A(y)$。例如，对于 $2021$，集合 $A(2021)$ 包含整数 $122, 212, 221, 1220, 2120, 2210, 1202, 2102, 2201, 1022, 2012$ 和 $2021$。注意，集合 $A(y)$ 总是包含 $y$ 本身，因此它永远不会为空。

对于任意正整数 $x$，我们定义 $S(x)$ 为所有满足以下条件的正整数 $z$ 的集合：$A(z)$ 中所有整数的最大公约数等于 $x$。

给定整数 $n$，请找出 $S(n)$ 中的最小整数 $z$，或者判断 $S(n)$ 是否为空。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 50$)，表示测试用例的数量。 每个测试用例包含一个整数 $n$ ($1 \le n \le 10^{18}$)。

输出格式

对于每个测试用例，在单独的一行中输出一个整数。如果对应的集合 $S(n)$ 为空，输出 $-1$。否则，输出 $S(n)$ 中的最小元素。

样例

输入 1

2
12
2021

输出 1

48
-1