#include<fstream>

using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
unsigned long long fact(int y)
{
    unsigned long long p=1,j=1;
    for(int i=2;i<=y;i++)
    {
        p=p*i;
        j=j*p;
    }
    return j;
}
int main()
{
    for(int i=1;i<=10;i++)
    {
        int n,b,count=0;
        unsigned long long x;
        f>>n>>b;
        x=fact(n);
        int ok=1;
        while(ok)
        {
            if(x%b==0)
            {
                count++;
                x=x/b;
            }
            else
                ok=0;
        }
        g<<count<<"\n";
    }
    return 0;
}