#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;


#define inf 0x3f3f3f3f

long long N, B;

long long solve(long long N, long long P)
{
     long long i, k = 0, r = 0;
     for(i = P; i <= N; i *= P)
     {
           k = N / i;
           r += 1LL * i * k * (k - 1) / 2;
           r += 1LL * (N - k * i + 1) * k;
     }
     return r;
}

int main()
{
    freopen("zero2.in", "r", stdin);
    freopen("zero2.out", "w", stdout);
    long long i, res, j, k;
    for(i = 0; i < 10; i++)
    {
          scanf("%lld %lld", &N, &B);
          res = inf; res *= res;
          for(j = 2; j * j <= B; j++)
          {
                if(B % j) continue;
                for(k = 0; !(B % j); B /= j) k ++;
                res = min(res, solve(N, j) / k);
          }
          if(B > 1) res = min(res, solve(N, B));
          printf("%lld\n", res);
    }
    return 0;
}