幽默，普及 T2 ，绿题。

幽默，比赛讲评，抽象做法。

幽默，364B 代码，赛时通过率 $14.11\%$。

题目很简单，就不解释了。

在下文中，设初始输入的数为 $n,m$，则我们令 $b = \frac{n}{m}$。将 $n$ 和 $b$ 分别分解质因数，得 $n=p_1^{q_1}\times p_2^{q_2}\times\dots\times p_k^{q_k},b=r_1^{s_1}\times r_2^{s_2}\times\dots\times r_l^{s_l}$。那么，这意味着，我们使 $n$ 乘到 $m$，就需要将 $b$ 分解成若干个数相乘的形式，然后让 $n$ 依次乘它们。

那么考虑贪心，为了使得从 $n$ 变成 $m$ 的次数最小，每次乘的数需要尽量大，而且必须同时是 $b$ 的因数和 $n$ 的因数，因为如果该数不是 $b$ 的因数，那么乘出来的数显然永远不可能变成 $m$；如果该数不是 $n$ 的因数，显然就无法进行该次操作。

那么，既为 $n$ 的因数又为 $b$ 的因数的数里面最大的一个，显然是 $\gcd(n,b)$。所以最优的策略就是每次让 $n \gets n \times \gcd(n,b),b \gets \frac{b}{\gcd(n,b)}$。于是我们这样循环往复操作就可以了。注意：如果在乘的过程中出现了 $\gcd(n,b)$ = 1，那么显然无解，因为这样就进入了死循环，永远都不能到达 $b$ 了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	int t; cin >> t;
	while(t--) { 
		ll n,m; cin >> n >> m;
		bool flag = 0;
		ll bei = m / n, cnt = 0;
		while(n != m) {
			ll g = __gcd(bei,n);
			if(g == 1) { flag = true; break; }
			n *= g; bei /= g; cnt++;
		}
		cout << (flag ? -1 : cnt) << endl;
	}
	return 0;
}