#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;
bool mark[1005];
vector<int>prime,prime1;
int sum[1005];
void make_prime(){
    int j,k;
    for(j=2;j<=1000;j++){
        for(k=2;k*j<=1000;k++){
            mark[j*k]=1;
        }
    }
    for(j=2;j<=1000;j++){
        if(!mark[j]) prime.push_back(j);
    }
}
int main(){
    make_prime();
    int T;
    scanf("%d",&T);
    while(T--){
        memset(sum,0,sizeof(sum));
        prime1.clear();
        int n;unsigned long long m;
        int ok=0,ok1=0;
        cin>>n>>m;
        if(n==m) ok=1;
        if(m%n) ok1=1;
        else m/=n;
        int j,k,i;
        for(j=0;j<prime.size();j++){
            if(prime[j]>n) break;
            if(n%prime[j]==0){
                prime1.push_back(prime[j]);
                while(n%prime[j]==0){
                    sum[prime1.size()-1]++;
                    n/=prime[j];
                }
            }
        }
        if(n>1){
            prime1.push_back(n);
            sum[prime1.size()-1]++;
        }
        int ans=0;
        for(j=0;j<prime1.size();j++){
            int cnt=0;
            while(m%prime1[j]==0){
                m/=prime1[j];
                cnt++;
            }
            int t=0,now=0;
            while(now<cnt){
                now+=sum[j];
                sum[j]+=sum[j];
                t++;
            }
            //printf("%d\n",t);
            ans=max(ans,t);
        }
        //printf("%d\n",m);
        if(ok) printf("0\n");
        else if(m!=1||ok1) printf("-1\n");
        else printf("%d\n",ans);
    }
    //system("pause");
    return 0;
}