RT

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define dbug(x) (void)(cerr << #x " = " << x << endl)


inline ll f(ll a,ll b){
	ll maxn = INT_MIN;
	for(ll i = 1;i * i <= a;i++){
		if(a % i == 0){
			if(b % (a / i) == 0){
				maxn = max(a/i,maxn);
				break;
			}
			if(b % i == 0){
				maxn = max(i,maxn);
			}
		}
	}
	if(maxn == INT_MIN || maxn == 1)
		return -1;
	else
		return maxn;
}


int main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0),cout.tie(0);
	ll t;
	cin >> t;
//	test
//	ll a;
//	cin >> a;
//	cout << f(t,a);

	while(t--){
		ll a,b;
		cin >> a >> b;
		if(b % a != 0){
			cout << -1 << endl;
			continue;
		}
		ll m = b / a;
		if(m == 1){
			cout << 0 << endl;
			continue;
		}
		ll temp = f(a,m);
		if(temp == -1){
			cout << temp << endl;
			continue;
		}
		ll cnt = 0;
		while(a < b){
			a *= temp;
			m = b/a;
			temp = f(a,m);
			cnt++;
		}
		cout << cnt << endl;
	}

	
	return 0;
}