#include<fstream>
#include<algorithm>
using namespace std;
ifstream f ("zero2.in");
ofstream g ("zero2.out");
long long i,zero,a,b,e;
long long rez(long long n,long long i)//desc in T!
{
    long long rez=0,t,k;
    for(t=i;t<=n;t*=i)
    {
        k=n/t;
        rez+=t*k*(k-1)/2+(n-k*t+1)*k;
    }
    return rez;
}
int main()
{
    for(int o=1;o<=10;++o)
    {
        f>>a>>b;
        zero=9223372036854775807;
        for(i=2;i*i<=b;++i)//parcurg div
        {
            if(b%i==0)
            {
                e=0;
                while(b%i==0)
                {
                    ++e;
                    b/=i;
                }
                zero=min(zero,rez(a,i)/e);//nr zero
             }
        }
        if(b>1) zero=min(zero,rez(a,b));//nr zero
        g<<zero<<'\n';
    }
    return 0;
}