#include <iostream>
#include <fstream>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;

long long n, b;

long long s(long long n, long long p)
{
    long long sol,k;

    k=1LL*(n/p-1);

    sol=p*(k+1)*k/2;
    sol=sol+(k+1)*(n-(k+1)*p+1);

    return sol;
}

long long minim(long long a, long long b)
{
    if(a<b) return a;
    return b;
}

long long f(long long n, long long p)
{
    long long answer=0;

    for( ; 1<=n/p; p=p*p)
    {
        answer+=s(n,p);
    }

    return answer;

}

int factorizare(long long b)
{
    long long i,e,answer=inf*inf;

    for(i=2; b!=1 ; i++)
    {
        if(b%i==0)
        {
            e=0;

            while(b%i==0)
            {
                e++;

                b=b/i;
            }
            answer=minim(answer, f(n,i)/e);

            //cout<<n<<' '<<i<<' '<<f(n,i)<<endl;
        }
    }

    return answer;
}

int main()
{
    ifstream in("zero2.in");
    ofstream out("zero2.out");

    int i;

    for(i=1; i<=10; i++)
    {
        in>>n>>b;
        out<<factorizare(b)<<endl;
    }

    return 0;
}