#include<stdio.h>
#include<fstream.h>
#include<math.h>
#define nmax 1000
int long prim[nmax],numar[nmax];
long long rezolva(int long,int long); void desc(int long);long long s(int long n, int long p);


int main()
 {int i;
  int long a,b;
 freopen("zero2.in","r",stdin);
 freopen("zero2.out","w",stdout);

 for(i=1;i<=10;i++)
   {scanf("%ld%ld",&a,&b);
	printf("%lld\n",rezolva(a,b));
	}
 fclose(stdout);
 return 0;
 }

long long rezolva(int long n,int long b)
{long long nr[nmax],i,min,p;
 memset(nr,0,sizeof(nr));
 desc(b);

 for(i=1;i<=prim[0];i++)
  {for(p=prim[i];p<=n;p*=prim[i])
	 nr[i]+=s(n,p);
   nr[i]/=numar[i];
   }
 for(i=2,min=nr[1];i<=prim[0];i++)
  if(nr[i]<min)
   min=nr[i];
  return min;
  }

long long s(int long n, int long p)
{int long k;
 k=n/p-1;
 return (k+1)*(n-(k+1)*p+1)+(k+1)*k*p/2;
 }

void desc(int long x)
{int d;
 memset(prim,0,sizeof(prim));
 memset(numar,0,sizeof(numar));

 for(d=2;d<=sqrt(x);d++)
   if(!(x%d))
	 {prim[++prim[0]]=d;
	  while(!(x%d))
		{x/=d;
		 numar[prim[0]]++;
		 }
	 }
 if(x>1)
  {prim[++prim[0]]=x;
   numar[prim[0]]++;
   }
}