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

int n,baza,i,j,a[1000000],b[1000000],s,nr,min,p,k;

int main()
{
	freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    for (i=1;i<=10;++i)
    {
     	scanf("%d %d",&n,&baza);
        p=0;
        nr=int(sqrt(baza));
        for (j=2;j<=nr;++j)
        {
        	if (baza%j==0)
            {
            	p++;
                a[p]=j;
                b[p]=1;
                baza/=j;
	            while (baza%j==0)
     		    {
            	 	baza/=j;
                    b[p]++;
            	}
            }
        }
        if (baza>1)
        {
         	p++;
            a[p]=baza;
            b[p]=1;
        }

        min=10000;
        for (j=1;j<=p;++j)
        {
        	nr=0;
            while (a[j]<=n)
            {
            	k=n/a[j]-1;
            	s=k*(k+1)/2*a[j]+(k+1)*(n-(k+1)*a[j]+1);
                nr+=s;
                a[j]*=a[j];
            }
            if (min>nr/b[j]) min=nr/b[j];
        }
        printf("%d\n",min);
    }
    
    return 0;
}