#include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<map>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int _max=1e3+;

 ll n,s,t;

 map<ll,int> mp;

 map<ll,int>::iterator it;

 void divide(ll n)

 {

     mp.clear();

     t=;

     for(ll i=;i*i<=n;i++){

         if(n%i==){

             mp[i]++;

             n/=i;

             while(n%i==){

                 mp[i]++;

                 n/=i;

             }

         }

     }

     if(n!=) mp[n]++;

 }

 ll judge(ll p){

     ll cnt=;

     ll now=n;

     while(now){

         cnt+=now/p;

         now/=p;

     }

     return cnt;

 }

 ll solve()

 {

     ll ans= 9223372036854775807ll;

     for(it=mp.begin();it!=mp.end();it++){

         ans=min(judge(it->first)/it->second,ans);

     }

     return ans;

 }

 int main()

 {

     int T;

     cin>>T;

     while(T--){

         scanf("%lld%lld",&n,&s);

         divide(s);

         printf("%lld\n",solve());

     }

     return ;

 }