#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    freopen("zero2.in", "r", stdin);
    freopen("zero2.out", "w", stdout);
    int n, b, p, exp, i, m=10;
    long long sol, x, k, ret;
    while(m--)
    {
        scanf("%d %d", &n, &b);
        for(i=2; i*i<=b; i++)
        if(b%i==0)
        {
            p=i;
            for(exp=0; b%i==0; exp++)
                b=b/i;
        }
        if (b>1)
        {
            exp=1;
            p=b;
        }
        sol=ret=0;
        for(x=p; x<=n; x*=p)
            {
                k=n/x;
                sol=sol+x*(k-1)*k /2 + k * (n%x+1);
                ret+=sol/exp;
                sol%=exp;
            }
        printf("%lld\n", ret);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}