#include <fstream>
using namespace std;
ifstream in("zero2.in");
ofstream out("zero2.out");
int putere(int a, int div1)
{
    int nr=0;
    while (a%div1==0)
        {
            nr++;
            a/=div1;
        }
    return nr;
}
int main()
{
    long long f,b,cnt=2,nr=1;
    long long rez=0,sol=9223372036854775807,div;
    cnt=0;
    for (int i=1; i<=10; ++i)
    {
        in>>f>>b;
        long long q=b;
        div=2;
        while (div*div<=q)
        {
            while (b%div==0)
            {
                cnt++;
                b/=div;
            }
            if (cnt)
            {
                for (int k=div; k<=f; k+=div)
                    rez+=(f-k+1)*putere(k,div);
                sol=min(rez/cnt,sol);
            }
            cnt=0;
            div++;
            rez=0;
        }
        if (b!=1)
        {
            for (int k=b; k<=f; k+=b)
                rez+=(f-k+1)*putere(k,b);
            sol=min(sol,rez);
        }
        out<<sol<<'\n';
        nr=1;
        sol=9223372036854775807;
        rez=0;
    }
    return 0;
}