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