Reduce to 1 CodeChef Solution | CodeChef Problem Solution 2022

Reduce to 1 CodeChef Solution | CodeChef Problem Solution 2022 

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

To do so, he can perform the following move several times (possibly, zero):

• Pick two integers X$X$ and Y$Y$ such that X+Y$X+Y$ is even and XY$X^Y$ is a divisor of N$N$. Then, replace N$N$ by NXY${\displaystyle \frac{N}{X^Y}}$

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

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

Solution Click Below:- 

Input Format

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

Output Format

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

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤1018$1\le N\le {10}^{18}$

Sample Input 1 

2
25
24

Sample Output 1 

1
-1

Explanation

Chef and Chapters CodeChef Solution | CodeChef Problem Solution 2022

Presents for Cheffina CodeChef Solution | CodeChef Problem Solution 2022

Chef and Bird farm CodeChef Solution | CodeChef Problem Solution 2022

Valentine Vex CodeChef Solution | CodeChef Problem Solution 2022

Buying Sweets CodeChef Solution | CodeChef Problem Solution 2022

Reduce to 1 CodeChef Solution | CodeChef Problem Solution 2022

Three Arrays CodeChef Solution | CodeChef Problem Solution 2022

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

Join Now for Solution:- 

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