/// zero2


#include <fstream>



using namespace std;



long long p[101],d[101];



long long t,i,k,n,b,nr,j,Min,s;



int main() {

    ifstream f("zero2.in");

    ofstream g("zero2.out");

    for(t=10;t>0;t--) {

        f>>n>>b;

        k=0;

        for(i=2;i*i<=b;i++) {

            if(b%i==0) {

                k++;

                d[k]=i;

                p[k]=0;

                while(b%i==0) {

                    b/=i;

                    p[k]++;

                }

            }

        }

        if(b>1) {

            k++;

            d[k]=b;

            p[k]=1;

        }

        Min=(1LL<<62);

        for (i=1;i<=k;i++) {

            s=0;

            for(j=d[i];j<=n;j*=d[i]) {

                nr=n/j;

                nr=nr*(nr-1)/2*j+nr*(n-nr*j+1);

                s+=nr;

            }

            s/=p[i];

            if (s<Min) {

                Min=s;

            }

        }

        g<<Min<<"\n";

    }

    return 0;

}