#include <iostream>
#include <fstream>
using namespace std;
ifstream in("zero2.in");
ofstream out("zero2.out");
 
const int nmax = 100006;
long long n, b, nrap, prim[nmax], put[nmax];
 
void descompune() {
    nrap = 0;
    int chestie;
    for (int i = 2; i * i<=b; i++)
	{
        chestie = 0;

        while(b%i==0)
		{
            b /= i;
			chestie++;
        }

        if (chestie != 0) 
		{
			nrap++;
            prim[nrap] = i;
            put[nrap] = chestie;
        }
    }

    if(b!=1) 
	{
		nrap++;
        prim[nrap] = b;
        put[nrap] = 1;
    }
}
 
 
int nrzt()
{
    long long chestie, ac, rasp, minim = 2000000000000000000;
    for(int i = 1; i <=nrap; i++)
	{
        rasp = 0;
        chestie = prim[i];

        while(chestie<=n)
		{
            ac = n / chestie;
            rasp = rasp + (ac - 1) * ac / 2 * chestie + ac * (n - ac * chestie + 1);
            chestie *= prim[i];
        }

        if (rasp/put[i]<=minim)
			minim = rasp / put[i];
    }

    return minim;
}
 
int main(){
    int player_unu=0;

    for(int shp = 0; shp<10; shp++)
	{
        in>>n>>b;

        descompune();
        out<<nrzt()<<'\n';
    }

    return player_unu;
}