#include <fstream>
#include <cstring>
#define MAX 31634
#define NPRIME 3405
using namespace std;
ifstream fin("zero2.in");
ofstream fout("zero2.out");
int x,y,z;
long long int k,kmin,cp,p;
bool Primal[MAX];
int Prim[NPRIME],nrprim=1;
int main(){
    long long int i,j,q;
    Prim[0]=2;
    for(i=3;i<200;i+=2){
        if(Primal[i]==0){
            Prim[nrprim++]=i;
            for(j=i*i;j<MAX;j+=i)Primal[j]=1;
        }
    }
    for(i=201;i<MAX;i+=2)if(Primal[i]==0)Prim[nrprim++]=i;
    for(i=0;i<10;++i){
        fin>>x>>y;
        kmin=9999999999;
        for(j=0;j<nrprim&&Prim[j]*Prim[j]<=y;++j){
            if(y%Prim[j]==0){
                p=0;
                k=0;
                while(y%Prim[j]==0){
                    ++p;
                    y/=Prim[j];
                }
                for(q=2;q<=x;++q){
                    cp=Prim[j];
                    while(q>=cp){
                        k+=q/cp;
                        cp*=Prim[j];
                    }
                }
                k=k/p;
                if(kmin>k)kmin=k;
            }
        }
        if(y!=1){
            k=0;
            for(q=2;q<=x;++q){
                cp=y;
                while(q>=cp){
                    k+=q/cp;
                    cp*=y;
                }
            }
            if(kmin>k)kmin=k;
        }
        fout<<kmin<<'\n';
    }
    return 0;
}