给你一个整数$$$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