T2

30 分

暴力搜索即可。

60 分

显然变换过程中数一定变小，记忆化搜索即可。

正解

显然如果 $n$ 中存在除了 $2,3,5$ 的其他质因子，必定无解。

考虑三种变换的实质。

操作 $1$：去掉当前数中的 $1$ 个质因子 $2$。

操作 $2$ ：将当前数中的质因子 $2$ 增加 $1$ 个，去掉当前数中的 $1$ 个质因子 $3$。

操作 $3$ ：将当前数中的质因子 $2$ 增加 $2$ 个，去掉当前数中的 $1$ 个质因子 $5$。

那么做法就出来了，一个质因子 $2$ 贡献为 $1$，质因子 $3$ 贡献为 $2$，质因子 $5$ 贡献为 $3$。

复杂度 $\mathcal{O}(T\log n)$。

#include<iostream>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        long long n;
        cin>>n;
        int cnt2=0,cnt3=0,cnt5=0;
        while(n%2==0){
            cnt2++;
            n/=2;
        }
        while(n%3==0){
            cnt3++;
            n/=3;
        }
        while(n%5==0){
            cnt5++;
            n/=5;
        }
        if(n!=1){
            cout<<-1<<endl;
            continue;
        }
        int steps=0;
        steps+=cnt5;
        cnt2+=2*cnt5;
        steps+=cnt3;
        cnt2+=cnt3;
        steps+=cnt2;
        cout<<steps<<endl;
    }
    return 0;
}