#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SIZE(X) (int)((X).size())
#define TIPA(a, i) (cerr << #a << "[" #i " = " << (i) << "] = " << (a)[i] << endl)
#define TIP(x) (cerr << #x << " = " << (x) << endl)

#define MP make_pair
#define PB push_back
#define INF 0x3f3f3f3f

typedef unsigned long long ULL;

using namespace std;

int N, B;
int nr, p[32], e[32];
ULL R;
/*            
            int k = N/p[i], r = p[i]*(k-1)*k/2;
            r += (N - k*p[i] + 1) * k;
*/

ULL baga(ULL N, ULL x)
{
    ULL r = 0, k;
    for (ULL p = x; p <= N; p *= x)
    {
        k = N/p, r += p*(k-1)*k/2;
        r += (N - k*p + 1)*k;
    }
    return r;
}

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

    REP(t, 10)
    {
        scanf("%d %d", &N, &B);
        memset(e, 0, sizeof(e));
        memset(&R, 0xFF, sizeof(R));
        nr = 0;
        
        for (int i = 2; i * i <= B; i ++)
            if (B%i == 0)
            {
                p[nr] = i;
                for (; B%i == 0; B /= i) ++ e[nr];
                ++ nr;
            }
        if (B > 1)
            p[nr] = B, e[nr] = 1, ++ nr;

        REP(i, nr)
        {
            ULL r = baga(N, p[i]);
            if (R > r/(ULL)e[i])
                R = r/(ULL)e[i];
        }

        printf("%lld\n", R);
    }
    return 0;
}