问题2493--整数的最优变换

2493: 整数的最优变换

时间限制: 1 Sec  内存限制: 128 MB
提交: 237  解决: 84
[提交] [状态] [讨论版] [命题人:]

题目描述

给定一个整数 n，这里定义了如下操作： 
  1. 如果 n 能被 2 整除，n = n / 2;
  2. 如果 n 能被 3 整除，n = 2 * n / 3;
  3. 如果 n 能被 5 整除，n = 4 * n / 5。
举例说明，对于整数 30，可以通过第 1 个操作转换成15，也可以通过第 2 个操作转换成 20，也可以通过第 3 个操作转换成 24。
这里的任务是计算出给定 n 转换成 1 的最少操作步数，也有可能 n 根本无法转换成 1。

输入

第一行仅有一个整数 q (1 ≤ q ≤ 1000)，代表询问数。
接下来 q 行，每行一个正整数 n (1 ≤ n ≤ 1018) 表示一次询问。

输出

输出 q 行，每行一个整数表示对应的询问的答案。如果 n 确实无法转换成 1，对应答案请输出 -1。

样例输入

7
1
10
25
30
14
27
1000000000000000000

样例输出

0
4
6
6
-1
6
72

来源/分类

https://codeforces.com/problemset/problem/1176/A 

[提交] [状态]