#include <bits/stdc++.h>

using namespace std;

vector <int> primeNumbers;
bool isNotPrime[100001];

void buildCiur () {
    for (int i = 2; i <= 100000; ++i) {
        if (!isNotPrime[i]) {
            primeNumbers.push_back(i);
            for (int j = i + i; j <= 100000; j += i) {
                isNotPrime[j] = true;
            }
        }
    }
}

long long solve (int n, int b) {
    long long result = (1LL << 60);
    for (auto x : primeNumbers) {
        if (1LL * x * x > b) {
            break;
        }
        if (b % x) {
            continue;
        }
        int exponent = 0, auxiliar = 1;
        long long current = 0;
        while (b % x == 0) {
            b /= x;
            exponent += 1;
        }
        while (1LL * auxiliar * x <= n) {
            auxiliar *= x;
            int bariera = (n / auxiliar) - 1;
            int rest = n % auxiliar + 1;
            current += 1LL * auxiliar * bariera * (bariera + 1) / 2;
            current += 1LL * (bariera + 1) * rest;
        }
        result = min (result, current / exponent);
    }
    if (b > 1) {
        int exponent = 0, auxiliar = 1, x = b;
        long long current = 0;
        while (b % x == 0) {
            b /= x;
            exponent += 1;
        }
        while (1LL * auxiliar * x <= n) {
            auxiliar *= x;
            int bariera = (n / auxiliar) - 1;
            int rest = n % auxiliar + 1;
            current += 1LL * auxiliar * bariera * (bariera + 1) / 2;
            current += 1LL * (bariera + 1) * rest;
        }
        result = min (result, current / exponent);
    }
    return result;
}

int main() {
    ifstream fin ("zero2.in");
    ofstream fout ("zero2.out");
    buildCiur();
    for (int i = 1; i <= 10; ++i) {
        int n, b;
        fin >> n >> b;
        fout << solve (n, b) << '\n';
    }
    return 0;
}