#include<stdio.h>
#include<math.h>

long long n, b, f, nr, ex, min, fminim,contor, d[5000], p;
char u[5000]

void ciur()
{
 memset(u,'0',sizeof(u));
  for (i=2; i<=5000; i++)
    {
      if (u[i]=='0') 
  	{
	  d[++p]=i;
	  j=2;
	  while (i*j<5000) u[i*(j++)]='1';
	}
    }
}

long div(long x)
{
  long i,r;
  for (i=1;d[i]*d[i]<=x && i<=p; i++)
    {
      r=0;
      while (x%d[i]==0)	r++,x/=d[i];
      fminim=d[i];
    }
  if (x!=1) fminim=x;
  return fminim;
}

/*
int prim(long long x)
{
  if (x==1 || x==0) return 0;
  if (x==2) return 1;
  for (long long i=3; i<=x/2; i+=2)
    if (x%i==0) return 0;
  return 1;
}

void descomp(long long x)
{
  long long y=x, k; min=1000;
  fminim=0;
  if (y%2==0)
    fminim=2;
  for (long long i=y; i=3; i-=2)
    {
      if (y%i==0)
	if (prim(i))
	  fminim=i; break;
	  
    }
}
*/

int main()
{
  long long i,z,k,p;
  freopen("zero2.in","r",stdin);
  freopen("zero2.out","w",stdout);
  long long nr;
  for (z=1; z<=10; z++)
    {
      scanf("%lld %lld",&n, &b);
      fminim=div(b);
      k=floor(n/fminim)-1;
      while (pow(fminim,p)<=n)  contor+=(k*(k+1)/2*pow(fminim,p) + (k+1)*(n-(k+1)*pow(fminim,p)+1));
      printf("%lld\n",contor);
    }
  return 0;
}