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