← 返回题目列表

Codeforces · 1374/B

B. 乘以 2,除以 6

中文机器翻译题面 查看原题

给你一个整数$$$n$$$。一步操作中,您可以将 $$$n$$$ 乘以 2,也可以将 $$$n$$$ 除以 $$$6$$$(如果它能被 $$$6$$$ 整除而没有余数)。

你的任务是找出从 $$$n$$$ 获得 $$$1$$$ 所需的最少移动次数,或者确定是否不可能做到这一点。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$)。

输出

对于每个测试用例,打印答案 - 如果可以从 $$$n$$$ 获得 $$$1$$$ 所需的最少移动次数,如果不可能从 $$$n$$$ 获得 $$$1$$$ 则为 -1。

示例

输入 #1

7
1
2
3
12
12345
15116544
387420489

输出 #1

0
-1
2
-1
-1
12
36

注意

考虑示例的第六个测试用例。可以通过以下从给定整数 $$$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$$$。