#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

typedef unsigned long long ll;

const ll oo = 1LL << 63;

ll sol,n,b;

ll num(ll x,ll y)
{
    ll cnt = 0;

    for (ll i = y;i <= n;i *= y)
    {
        ll aux = (x / i) - 1;
        cnt += aux * (aux + 1) * i / 2 + (aux + 1) * (x - (aux + 1) * i + 1);
    }

    return cnt;
}

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

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

         for (ll i = 2;i * i <= b;i++)
             if (b % i == 0)
             {
                 ll cnt = 0;

                 while (b % i == 0)
                       cnt++,b /= i;

                 sol = min(sol,num(n,i) / cnt);
             }

         if (b != 1)
            sol = min(sol,num(n,b));

         printf("%lld\n",sol);
     }

  return 0;
}