## [Coding] Reduce to 1 solution codechef

Arun has an integer NN. His friend Sucksum likes the number 11, so Arun wants to reduce NN to 11.

## [Coding] Reduce to 1 solution codechef

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

- Pick two integers XX and YY such that X+YX+Y is even and XYXY is a divisor of NN. Then, replace NN by NXYNXY

Note that at each step, XYXY only needs to be a divisor of the *current* value of NN, and not necessarily a divisor of the integer Arun initially started with.

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

## [Coding] Reduce to 1 solution codechef

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

### Output Format

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

## [Coding] Reduce to 1 solution codechef

- 1≤T≤1051≤T≤105
- 1≤N≤10181≤N≤1018

### Sample Input 1

```
2
25
24
```

### Sample Output 1

```
1
-1
```

## Reduce to 1 solution codechef Explanation

**Test case 11:** Choose X=25X=25 and Y=1Y=1. X+Y=26X+Y=26 is even, and XY=25XY=25 is a divisor of N=25N=25 so this is a valid choice of XX and YY. Dividing NN by XYXY leaves us with 2525=12525=1 and we are done.

**Test case 22:** It can be shown that no matter which moves are made, 2424 cannot be reduced to 11.