#include<stdio.h>
#include<math.h>
long i,n,b,j,p[10000000],e[10000000],lp;
long long m,q;
long long s(long n,long long p)
{long long k;
 k=(n/p)-1;
 return ((k*(k+1))/2)*p+(k+1)*(n-(k+1)*p+1);
}
long long nr(long n,long p)
{long long ss,x;
 x=1;
 ss=0;
 while(x*p<=n){x*=p;ss+=s(n,x);}
 return ss;
}
int main()
{
 freopen("zero2.in","r",stdin);
 freopen("zero2.out","w",stdout);
 for(i=1;i<=10;++i)
    {
     scanf("%ld%ld",&n,&b);
     for(j=2;j<=sqrt(b);++j)
        if(b==1)break;
           else if(b%j==0){p[++lp]=j;e[lp]=0;while(b%j==0){b/=j;++e[lp];}}
     if(b>1)
       {p[++lp]=b;
        e[lp]=1;}
     m=2000000000;
     for(j=1;j<=lp;++j)
        {
         q=nr(n,p[j])/e[j];
         if(m>q)m=q;
        }
     printf("%ld\n",m);
     lp=0;
    }
 return 0;
}