#include<fstream>
#include<bitset>
using namespace std;
ifstream in ("zero2.in");
ofstream out ("zero2.out");
bitset<1000000001>ciur;
int v[300000],cnt=2,nr,basa;
int main ()
{
    ciur[1]=1;
    v[1]=2;
    for (int i=4; i<=1000000001; i+=2)
        ciur[i]=0;
    for (int i=3; i*i<=1000000001; i+=2)
        if (!ciur[i])
        {
            v[cnt++]=i;
            for (int j=i*i; j<=1000000001; j+=i)
                ciur[j]=0;
        }
    for (int i=10; i>0; --i)
    {
        in>>nr>>basa;
        int a=basa,d=v[1],sol=999999999,k=1;
        cnt=0;
        while (d*d<=a)
        {
            while(basa%d==0)
            {
                cnt++;
                basa/=d;
            }
            int x=0;
            if (cnt)
            {
                for (int p=d; p<=nr; p+=d)
                    x+=(nr-p+1)*p/d;
                x/=cnt;
                cnt=0;
                sol=min(sol,x);
            }
            d=v[++k];
        }
        if (basa>1)
        {
            a/=(a/basa);
            int x=0;
            for (int p=a; p<=nr; p+=a)
                x+=(nr-p+1)*p/a;
            sol=min(sol,x);
        }
        out<<sol<<'\n';
    }
}