#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<limits.h>
using namespace std;
typedef unsigned long long UINT;
const int maxn = 1e6+2000;
UINT prime[maxn];
void getprime(){
    prime[0] = 1; prime[1] = 1;
    for(UINT i = 2; i*i <= maxn-10; i++){
        if(!prime[i])
        for(int j = i*i; j <= maxn-10 ;j += i){
            prime[j] = 1;
        }
    }
}
int main(){
    int T;
    getprime();
    scanf("%d",&T);
    UINT a,b;
    while(T--){
        scanf("%llu%llu",&a,&b);
        if(b < a){
            puts("-1");
        }else if(b == a){
            puts("0");
        }else{
            if(a == 1 || b%a != 0){
                puts("-1");
            }else{
                b /= a;
                int sum = 0;
                for(UINT i = 2; i <= maxn-100; i++){
                    if(prime[i]) continue;
                    UINT tmp = 1 , times = 0;
                    if(a % i != 0) continue;
                    while(a % i == 0){
                        a /= i;
                        tmp *= i;
                    }
                    while(b % tmp == 0){
                        b /= tmp;
                        tmp *= tmp;
                        times ++;
                    }
                    if(b % i == 0){
                        sum = times+1 > sum? times+1:sum;
                        while( b % i == 0){
                            b /= i;
                        }
                    }else{
                        sum = times > sum? times:sum;
                    }
                    if(b == 1){
                        break;
                    }
                }
                if(b == 1){
                    printf("%d\n",sum);
                }else{
                    puts("-1");
                }
            }
        }
    }
    return 0;
}