codeforces#P1374B. Multiply by 2, divide by 6

Multiply by 2, divide by 6

Description

You are given an integer $n$. In one move, you can either multiply $n$ by two or divide $n$ by $6$ (if it is divisible by $6$ without the remainder).

Your task is to find the minimum number of moves needed to obtain $1$ from $n$ or determine if it's impossible to do that.

You have to answer $t$ independent test cases.

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($1 \le n \le 10^9$).

For each test case, print the answer — the minimum number of moves needed to obtain $1$ from $n$ if it's possible to do that or -1 if it's impossible to obtain $1$ from $n$.

Input

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($1 \le n \le 10^9$).

Output

For each test case, print the answer — the minimum number of moves needed to obtain $1$ from $n$ if it's possible to do that or -1 if it's impossible to obtain $1$ from $n$.

Samples

7
1
2
3
12
12345
15116544
387420489
0
-1
2
-1
-1
12
36

Note

Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given integer $15116544$:

  1. Divide by $6$ and get $2519424$;
  2. divide by $6$ and get $419904$;
  3. divide by $6$ and get $69984$;
  4. divide by $6$ and get $11664$;
  5. multiply by $2$ and get $23328$;
  6. divide by $6$ and get $3888$;
  7. divide by $6$ and get $648$;
  8. divide by $6$ and get $108$;
  9. multiply by $2$ and get $216$;
  10. divide by $6$ and get $36$;
  11. divide by $6$ and get $6$;
  12. divide by $6$ and get $1$.