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.
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}$$$).
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)$$$.
2 12 2021
48 -1