#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
unsigned long long n,m,a[100000],b[100000];
int main(){
    unsigned long long tt;scanf("%llu",&tt);
    for (;tt--;){
        scanf("%llu%llu",&n,&m);unsigned long long ans=0,an=0;
        for (unsigned long long i=2;i*i<=n;i++){
            if (n%i==0){
                a[++an]=i;b[an]=0;
                while (n%i==0){n/=i;b[an]++;}
            }
        }
        if (n!=1){a[++an]=n;b[an]=1;}
        for (unsigned long long i=1;i<=an;i++){
            unsigned long long num=0;
            while (m%a[i]==0){
                m/=a[i];num++;
            }
            if (num<b[i]){m=233;break;}
            unsigned long long td=0;
            while (b[i]<num){b[i]*=2ll;td++;}
            ans=max(ans,td);
        }
        if (m!=1) puts("-1");
        else printf("%llu\n",ans);
    }
}