题目描述

给定一个整数 $n$。每一步操作，你可以将 $n$ 乘以 $2$，或者如果 $n$ 能被 $6$ 整除，则可以将 $n$ 除以 $6$。

你的任务是找出将 $n$ 变为 $1$ 所需的最少操作次数，或者判断是否无法做到这一点。

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

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来有 $t$ 行，每行一个整数 $n$（$1 \le n \le 10^9$）。

输出格式

对于每个测试用例，输出一个答案——将 $n$ 变为 $1$ 所需的最少操作次数；如果无法做到，则输出 $-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$。

由 ChatGPT 4.1 翻译

样例

7
1
2
3
12
12345
15116544
387420489

0
-1
2
-1
-1
12
36