#include <iostream>
#include <fstream>
using namespace std;

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

long long n,b,ddd,bc,contor,d,suma;

long long nr(long long n,long long b)
{
    long long put = b,rez=0;
    while(n/put!=0)
    {
        rez+= n/put;
        put *=put;
    }
    return rez;
}

void rez(long long n, long long b)
{
    contor = 0;
    ddd  = 0;
    d = 3;
    bc = b;
    if(bc%2==0) { contor =0;ddd = 2;}
    while(bc%2==0) { contor++;bc=bc/2;}
    while(d*d<=bc)
    {
        if(bc%d==0)
        {
            ddd = d;
            contor = 0;
            while(bc%d==0)
            {
                contor++;
                bc = bc/d;
            }
        }
        d+=2;
    }
    if(bc!=1){ddd = bc;contor = 1;}
    suma = 0;
    for(int i=1;i<=n;i++)
    {
        suma += nr(i,ddd);
    }
    out << suma/contor << "\n";
}

int main()
{
    for(int i=0;i<10;i++)
    {
        in >> n >> b;
        rez(n,b);
    }
    return 0;
}