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