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)$。