#include <fstream>
#define MAXV 32000
using namespace std;
ifstream in ("zero2.in");
ofstream out ("zero2.out");

unsigned long long c[40000],k,fact[40000],mini,c2[40000];
unsigned long long n,b;

int main()
{
    unsigned long long i,j,q,w;
    for(i=1;i<=10;i++)
    {
        in>>n>>b;
        k=0;mini=9223372036854775808;
        if(b%2==0)
        {
            fact[++k]=2;
            c[k]=1;
            c2[k]=0;
            b/=2;
            while(b%2==0)
                {
                    b/=2;
                    c[k]++;
                }
        }
        for(j=3;j<=MAXV and b!=1;j+=2)
            if(b%j==0)
            {
                fact[++k]=j;
                c[k]=1;
                c2[k]=0;
                b/=j;
                while(b%j==0)
                {
                    b/=j;
                    c[k]++;
                }
            }
        if(b!=1)
        {
            fact[++k]=b;
            c[k]=1;
        }
        for(j=2;j<=n;j++)
            for(q=1;q<=k;q++)
                for(w=fact[q];w<=j;w*=fact[q])
                    c2[q]+=(j/w);
        for(j=1;j<=k;j++)
            mini=min(mini,c2[j]/c[j]);
        out<<mini<<"\n";
    }
    return 0;
}