#include <fstream>
using namespace std;
ifstream fin("zero2.in");
ofstream fout("zero2.out");
int n,b,i,f[1005],p,nrf,v,x,k,r,j;
long long s,S;
int main()
{for(i=1;i<=10;++i)
    {fin>>n>>b;
    nrf=0;
    S=0;
     for(j=2;j*j<=b;j++)
        {if(b%j==0){v=1;S=0;
     //    fout<<j<<" ";
                    nrf++;f[nrf]=j;p=0;
                    while(b%j==0){p++;
                                  b=b/j;
                                 }
                    s=0;
         v=j*v;
       //  fout<<f[j]<<"( ";
         x=n/j;
         r=n%j;
         while(x!=0)
              {s=s+v*x*(x+1)/2;
               s=s-(v-1-r)*x;
               v=j*v;
               x=n/v;
               r=n%v;
              }
         s=s/p;
         if(nrf==1)S=s;
           else S=min(S,s);
        }
        }
     if(b>1){nrf++;f[nrf]=b;p=1;
             v=1;
   //  fout<<b<<" ";
             s=0;
         v=b*v;
       //  fout<<f[j]<<"( ";
         x=n/b;
         r=n%b;
         while(x!=0)
              {s=s+v*x*(x+1)/2;
               s=s-(v-1-r)*x;
               v=b*v;
               x=n/v;
               r=n%v;
              }
         s=s/p;
         if(nrf==1)S=s;
           else S=min(S,s);
             }
           // fout<<nrf<<"\n";
        fout<<S<<"\n";
      }
    }