#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;

}