CF1374B.Multiply by 2, divide by 6

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.

给你一个整数 $n$。在一次操作中，你可以将 $n$ 乘以 $2$，或者当 $n$ 能被 $6$ 整除时将其除以 $6$。

你的任务是求出从 $n$ 得到 $1$ 所需的最少操作次数；如果无法得到 $1$，则判定为不可能。

你需要回答 $t$ 个相互独立的测试用例。

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

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$）—— 表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例仅包含一行，其中有一个整数 $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$.

对于每个测试用例，输出答案——即从 $n$ 得到 $1$ 所需的最少操作次数；如果无法从 $n$ 得到 $1$，则输出 $-1$。

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

考虑示例中的第六个测试用例。答案可通过从给定整数 $15116544$ 出发执行以下操作序列得到：

1. 除以 $6$，得到 $2519424$；
2. 除以 $6$，得到 $419904$；
3. 除以 $6$，得到 $69984$；
4. 除以 $6$，得到 $11664$；
5. 乘以 $2$，得到 $23328$；
6. 除以 $6$，得到 $3888$；
7. 除以 $6$，得到 $648$；
8. 除以 $6$，得到 $108$；
9. 乘以 $2$，得到 $216$；
10. 除以 $6$，得到 $36$；
11. 除以 $6$，得到 $6$；
12. 除以 $6$，得到 $1$。