Multiply by 2, divide by 6

Description:

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$$$.

Sample Input:

7
1
2
3
12
12345
15116544
387420489

Sample Output:

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$$$.