#include <bits/stdc++.h>
#include <climits>

using namespace std;

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

pair<int, int> divv(int &n, int b){
    pair<int, int> x;
    x.first=b;
    x.second=0;
    while(n%b==0){
        n/=b;
        x.second++;
    }
    return x;
}

void factor(vector< pair<int, int> > &a, int b){
    if(b%2==0)
        a.push_back( divv(b, 2) );
    for(int i=3;1LL*i*i<=b;i+=2){
        if(b%i==0)
            a.push_back( divv(b, i) );
    }
    if(b>1)
        a.push_back({b,1});
}

long long int pof(long long int n,long long int p){
    long long int k=n/p,r=n%p;
    return r*k+k+p*(k-1)*k/2;
}

int main()
{
    long long a,b;
    for(int i=1;i<=10;++i){
        fin>>a>>b;
        long long int mini=numeric_limits<long long int>::max();
        vector< pair<int, int> > f;
        factor(f, b);
        for(int i=0;i<f.size();++i){
            long long int bas=f[i].first, han=bas, res=0;
            long long int po=f[i].second;
            while(han<=a){
                res+=pof(a, han);
                han*=bas;
                if(han<0)
                    break;
            }
            mini=min(mini,res/po);
        }
        fout<<mini<<'\n';
    }
    return 0;
}