Arun has an integer N. His friend likes the number 1, so Arun wants to reduce N to 1.

To do so, he can perform the following move several times (possibly, zero):
Pick two integers X and Y such that X+Y is even and X^{Y} is a divisor of N. Then, replace N by $\dfrac{N}{X^{Y}}$

Note that at each step, X^{Y} only needs to be a divisor of the current value of N, and not necessarily a divisor of the integer Arun initially started with.

Find the minimum number of moves Arun needs to reduce N to 1. If it is not possible to reduce N to 1 using the given operation, print -1 instead.

------ Input Format ------

• The first line of input will contain an integer T, denoting the number of test cases. The description of T test cases follows.
• Each test case consists of a single line of input containing one integer N.

------ Output Format ------

For each test case, output on a new line the answer — the minimum number of moves needed to reduce N to 1, or -1 if it is not possible to do so.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{18}$

----- Sample Input 1 ------
2
25
24

----- Sample Output 1 ------
1
-1
----- explanation 1 ------
Test case $1$: Choose $X = 25$ and $Y = 1$. $X+Y = 26$ is even, and $X^{Y} = 25$ is a divisor of $N = 25$ so this is a valid choice of $X$ and $Y$. Dividing $N$ by $X^{Y}$ leaves us with $\frac{25}{25} = 1$ and we are done.

Test case $2$: It can be shown that no matter which moves are made, $24$ cannot be reduced to $1$.

见题面

见题面