#include <algorithm>
#include <vector>
using namespace std;

#define INF (1<<31)-1
#define pb push_back
#define mp make_pair
#define ll long long
#define sc second
#define fs first

vector <pair <ll,ll> > d;
ll n,b,rez;

void solve ()
{
    ll i,x,nr;

    d.clear ();
    for (i=2; i*i<=b; ++i)
        if (b%i==0)
        {
            for (nr=0; b%i==0; b/=i)
                ++nr;
            d.pb (mp (i,nr));
        }
    if (b>1)
        d.pb (mp (b,1));
    rez=INF;
    for (i=0; i<(ll)d.size (); ++i)
    {
        nr=0;
        for (x=d[i].fs; n/x; x*=d[i].fs)
            nr+=(n/x-1)*(n/x)/2*x+(n/x)*(n-(n/x)*x+1);
      rez=min (rez,nr/d[i].sc);
    }
    printf ("%lld\n",rez);
}

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

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

    return 0;
}