← 返回题目列表

Codeforces · 1176/A

A. 分吧!

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

给你一个整数$$$n$$$。

您可以使用此数字执行任意(可能为零)次数的以下任何操作:

1. 如果 $$$n$$$ 能被 $$$2$$$ 整除,则将 $$$n$$$ 替换为 $$$\frac{n}{2}$$$;
2. 如果 $$$n$$$ 能被 $$$3$$$ 整除,则将 $$$n$$$ 替换为 $$$\frac{2n}{3}$$$;
3. 如果 $$$n$$$ 能被 $$$5$$$ 整除,则将 $$$n$$$ 替换为 $$$\frac{4n}{5}$$$。

例如,您可以使用第一个操作将 $$$30$$$ 替换为 $$$15$$$,使用第二个操作将 $$$20$$$ 替换为 $$$20$$$,或者使用第三个操作将 $$$24$$$ 替换。

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

您必须回答 $$$q$$$ 独立查询。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 1000$$$) — 查询数。

接下来的 $$$q$$$ 行包含查询。对于每个查询,您都会获得整数 $$$n$$$ ($$$1 \le n \le 10^{18}$$$)。

输出

在新行上打印每个查询的答案。如果无法从$$$n$$$获得$$$1$$$,则打印-1。否则,打印完成该任务所需的最少步数。

示例

输入 #1

7
1
10
25
30
14
27
1000000000000000000

输出 #1

0
4
6
6
-1
6
72