#include <stdio.h>

int a,b,nr,x,i,j;

int main()
{
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    for (i=1;i<=10;++i)
    {
        scanf("%d %d\n", &a,&b);
        x=1;
        nr=2;
        while(nr<=a)
        {
            for (j=2;j<=nr;++j)
                  x*=j;
            nr++;
        }
        nr=0;
        while(x%b==0)
        {   nr++;
            x/=b;
         }
    printf("%d\n", nr);
   }
return 0;
}