## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Reduce to 1 CodeChef Solution | CodeChef Problem Solution 2022

Arun has an integer $N$. His friend Sucksum 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 $\frac{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.

Solution Click Below:-

### 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\le T\le {10}^{5}$
• $1\le N\le {10}^{18}$

### Sample Input 1

2
25
24


### Sample Output 1

1
-1


### Explanation

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$2$: It can be shown that no matter which moves are made, 24$24$ cannot be reduced to 1$1$.