#include <fstream>

using namespace std;

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

long long S (int N, int p) {
    long long sol = 0;

    int i = p;
    for (; 1; i *= p) {
        int k = N / i;
        sol += 1LL * (N + 1) * k - 1LL * (k + 1) * k / 2 * i;
        if (N / i < p) break;
    }

    return sol;
}

long long Nr (int N, int p) {
    long long sol = 4611686018427387904;

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

        int n = 0;
        while (p % i == 0) {
            ++ n;
            p /= i;
        }
        sol = min (sol, S (N, i) / n);
    }
    if (p > 1)
        sol = min (sol, S (N, p));
    return sol;
}

int main () {

    for (int i = 1; i <= 10; ++ i) {
        int x, y;
        fin >> x >> y;
        fout << Nr (x, y) << "\n";
    }

    return 0;
}