#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <cassert>

using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main()
{
    int t,n,k; cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n >> k;
        int ans = 0;
        bool err = true;
        if (n == 1)
        {
            ans = 0;
        }
        else
        if (k == 1)
        {
            ans = -1;
            err = false;
        }
        else
        {


            for (int j = 2; j * j <= n; j++)
            {
                int cnt = 0;
                while (n % j == 0)
                {
                    n /= j;         cnt++;
                }



                if (cnt == 0) continue;

                int cnt1 = 0;


                while (k % j == 0)
                {
                    k /= j;
                    cnt1++;
                }




                if (cnt1 == 0)
                {
                    err = false;
                    break;
                }
                if (cnt <= cnt1)continue;
                ans = max(ans, (cnt - 1) / cnt1);
            }



            if (n > 1) {
                int cnt = 1;
                int cnt1 = 0;
                while (k % n == 0)
                {
                    k /= n;
                    cnt1++;

                }



                if (cnt1 == 0)
                {
                    err = false;
                }

                else if (cnt >= cnt1) ans = max(ans, (cnt - 1) / cnt1);
            }
        }



        if (err == false) cout << -1 << endl; else cout << ans + 1 << endl;;
    }
    return 0;
}