#include <fstream>
using namespace std;
ifstream in("zero2.in");
ofstream out("zero2.out");
long long formula(long long n)
{
    return n * (n + 1) / 2;
}
long long count(long long n, long long a)
{
    long long s = 0, nr = a;
    while(nr <= n)
    {
        s += nr * formula(n / nr - 1) + (n % nr + 1) * (n / nr);
        nr *= a;
    }
    return s;
}
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)
            {
                rez=count(f,div);
                sol=min(rez/cnt,sol);
            }
            cnt=0;
            if (div==2)
                div++;
            else
                div+=2;
            rez=0;
        }
        if (b!=1)
        {
            rez=count(f,div);
            sol=min(sol,rez);
        }
        out<<sol<<'\n';
        nr=1;
        sol=9223372036854775807;
        rez=0;
    }
    return 0;
}