#include <bits/stdc++.h>
using namespace std;

ifstream in("zero2.in");
ofstream out("zero2.out");

long long _solve(int n, int b)
{
    long long ans = 0;

    for (int i = b; true; i *= b) {
        int k = n / i;
        ans += 1LL * (n + 1) * k -
               1LL * (k + 1) * k / 2 * i;

        if (n / i < b)
            break;
    }

    return ans;
}

long long solve(int n, int b)
{
    long long ans = numeric_limits<long long> :: max();

    for (int i = 2; i * i <= b; ++i) {
        if (b % i) continue;

        int nr = 0;
        while (!(b % i))
            ++nr, b /= i;

        ans = min(ans, _solve(n, i) / nr);
    }

    if (b > 1)
        ans = min(ans, _solve(n, b));

    return ans;
}

int main(void)
{
    for (int i = 1; i <= 10; ++i) {
        int n, b;
        in >> n >> b;

        out << solve(n, b) << endl;
    }

    return 0;
}