https://hack.codingblocks.com/app/contests/1/137/problem
#include
using namespace std;
#define INT_MAX 100000000
int main(){
int t;
cin>>t;
while(t--){
int ans=INT_MAX;
int n,k;
cin>>n>>k;
int occur;
for(int i=2;i*i<=k;i++){
if(k%i==0){
occur=0;
while(k%i==0){
occur++;
k=k/i;
}
int count=0;
int p=i;
while(p<=n){
count=count+(n/p);
p=p*i;
}
ans=min(ans,count/occur) ;
}
}
if(k>1){
int count=0;
int p=k;
while(p<=n){
count=count+(n/p);
p=p*k;
}
ans=min(ans,count);
}
if(ans==INT_MAX){
ans=0;
}
cout<<ans<<endl;
}
}