E. Construct The Integer
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For any positive integer $$$y$$$ we define $$$A(y)$$$ as the set of all positive integers that are anagrams of $$$y$$$. Formally, we consider the sequence of all digits of $$$y$$$ in decimal representation without leading zeroes, then we apply all possible permutations to this sequence. For any permutation we throw away leading zeroes and assemble digits back to an integer. All integers that can be obtained that way belong to $$$A(y)$$$. For example, for $$$2021$$$ set $$$A(2021)$$$ consists of integers $$$122$$$, $$$212$$$, $$$221$$$, $$$1220$$$, $$$2120$$$, $$$2210$$$, $$$1202$$$, $$$2102$$$, $$$2201$$$, $$$1022$$$, $$$2012$$$ and $$$2021$$$. Note, that set $$$A(y)$$$ always contains $$$y$$$, thus it is never empty.

For any positive integer $$$x$$$ we define $$$S(x)$$$ as the set of all positive integers $$$z$$$ such that greatest common divisor of all integers in $$$A(z)$$$ equals $$$x$$$.

You are given the integer $$$n$$$, find the minimum integer $$$z$$$ in $$$S(x)$$$, or determine that $$$S(x)$$$ is empty.

Input

The first line of the input contains one integer $$$t$$$ ($$$1 \leq t \leq 50$$$) — the number of the test cases.

Each test case data consists of one integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).

Output

For each test case, print one integer on a separate line. If the corresponding set $$$S(n)$$$ is empty, print -1. Otherwise, print minimum element of $$$S(n)$$$.

Example
Input
2
12
2021
Output
48
-1