#include<bits/stdc++.h>
using namespace std;
int T;
long long n,m;
bool flag;
int main(){
	cin>>T;
	long long ans=0;
	while(T--){
		ans=0;
		cin>>n>>m;
		if(n==m){//不用变 
			cout<<0<<endl;
			continue;
		}
		if(m%n!=0||__gcd(n,m/n)==1){//变不了
			cout<<-1<<endl;
			continue;
		}
		while(n!=m){
			if(__gcd(n,m/n)==1){
				cout<<-1<<endl;
				flag=true;
				break;
			}
			n*=__gcd(n,m/n);
			ans++;
		}
		if(flag==false) cout<<ans<<endl;
	}
	return 0;
}