#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;}
    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;
 }