#include <cstdio>
#include <algorithm>
#include <vector>

#define x first
#define y second
#define LL long long

using namespace std;

vector< pair< int, int > > D;

void desc(int n){
    D.clear();
    if(n % 2 == 0){
        D.push_back(make_pair(2, 0));
        while(n % 2 == 0){
            ++D[0].y;
            n /= 2;
        }
    }
    for(int i = 3; i * i <= n && n != 1; i += 2)
        if(n % i == 0){
            D.push_back(make_pair(i, 0));
            int Size = D.size() - 1;
            while(n % i == 0){
                n /= i;
                ++D[Size].y;
            }
        }
    if(n > 1)
        D.push_back(make_pair(n, 1));
}

inline int solve(int n, int k){
    desc(k);///descompun baza
    int Ans = -1;
    for(vector< pair< int, int > >::iterator it = D.begin(); it != D.end(); ++it){
        LL Sol = 0, Number = (LL)it->x;
        while(Number <= n){
            LL c = (LL)n / Number;
            Sol += Number * c * (c - 1) / 2;
            Sol += (n - Number * c + 1) * c;
            Number *= it->x;
        }
        if(Ans == -1)
            Ans = Sol / it->y;
        else
            Ans = min(Ans, (int)Sol / (it->y));
    }
    return Ans;
}

int main(){
    freopen("zero2.in", "r", stdin);
    freopen("zero2.out", "w", stdout);
    for(int L = 1; L <= 10; ++L){
        int n, k;
        scanf("%d %d", &n, &k);
        printf("%d\n", solve(n, k));
    }
    return 0;
}