#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define inf 0x3f3f3f3f
using namespace std;

long long n, b;

long long s(long long n, long long p)
{
    long long sol,k;

    k=1LL*(n/p-1);

    sol=p*(k+1)*k/2;
    sol=sol+(k+1)*(n-(k+1)*p+1);

    return sol;
}

long long minim(long long a, long long b)
{
    if(a<b) return a;
    return b;
}

long long f(long long n, long long p)
{
    long long answer=0;

    for( ; 1<=n/p; p=p*p)
    {
        answer+=s(n,p);
    }

    return answer;

}

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

    long long i,j,answer,e;

    for(i=1; i<=10; i++)
    {
        scanf("%lld %lld", &n, &b);

        answer=inf; answer*=inf;

        for(j=2; j*j<=b; j++)
        {
            if(b%j==0)
            {
                for(e=0; !(b%j); b/=j) e++;

                answer=minim(answer, f(n,j)/e);
            }
        }

        if(b>1)
        {
            answer=minim(answer, f(n,b));
        }

        printf("%lld\n", answer);


    }

    return 0;
}