#include <fstream.h>
#include <iostream.h>
unsigned long p, imp, nr, x, i, n, b, j, y, ok;
int main()
{
ifstream f("zero2.in");
ofstream g("zero2.out");
for(i=1; i<=10; i++)
    {f>>n>>b;
    p=1; y=1;
    for(j=1; j<=n; j++)
       {y=y*j;
	p=p*y;}
    ok=1; x=0;
    while((p>=b)&&ok)
         {
	 if(p%b==0)
	 x++;
	 else
         ok=0;
         p=p/b;
         }
     g<<x;
    }
f.close();
g.close();
return 0;
 }