#include <fstream>
using namespace std;
long long p[101],d[101];
long long t,i,k,n,b,nr,j,mini,s;
int main()
{
    ifstream f("zero2.in");
    ofstream g("zero2.out");
    for(t=10;t>0;t--)
    {
        f>>n>>b;
        k=0;
        for(i=2;i*i<=b;i++)
        {
            if(b%i==0)
            {
                k++;
                d[k]=i;
                p[k]=0;
                while(b%i==0)
                {
                     b/=i;
                     p[k]++;
                     }
                     }
                     }
                     if(b>1)
                     {
                         k++;
                         d[k]=b;
                         p[k]=1;
                         }
                         mini=(1LL<<62);
                         for (i=1;i<=k;i++)
                         {

                             s=0;
                             for(j=d[i];j<=n;j*=d[i])
                             {
                                 nr=n/j;
                                 nr=nr*(nr-1)/2*j+nr*(n-nr*j+1);
                                 s+=nr;
                                 }
                                 s/=p[i];
                                 if (s<mini)
                                 {
                                     mini=s;
                                 }
                          }
                                     g<<mini<<"\n";
    }
                                     return 0;
}