#include <fstream>
#include <bitset>
using namespace std;
ifstream in("zero2.in");
ofstream out("zero2.out");
bitset<1000001>ciur;
int v[100001];
int putere(int a, int div1)
{
    int nr=0;
    while (a%div1==0)
        {
            nr++;
            a/=div1;
        }
    return nr;
}
int main()
{
    v[1]=2;
    int f,b,cnt=2,nr=1;
    for (int i=2; i<=1000001; i+=2)
        ciur[i]=1;
    for (int i=3; i*i<=1000001; i+=2)
        if(!ciur[i])
        {
            v[cnt++]=i;
            for (int j=i; j<=1000001; j+=i)
                ciur[j]=1;
        }
    int rez=0,sol=9999999,div;
    cnt=0;
    for (int i=1; i<=10; ++i)
    {
        in>>f>>b;
        int q=b;
        div=v[nr++];
        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=v[nr++];
            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=9999999;
        rez=0;
    }
    return 0;
}