program pz;
var  f,g:text;i,n,j,b,y,z,p,a,k:longint;
     v,q:array[1..1000]of longint;
begin
     assign(f,'zero2.in'); reset(f);
     assign(g,'zero2.out');rewrite(g);
     for a:=1 to 10 do begin
      readln(f,n,b);
      p:=24883200;k:=1;z:=0;
     for i:=7 to n do begin
      p:=p*k;
      for j:=1 to i do
       p:=p*j; end;
      if b=10  then
       while p mod 10=0 do begin
       z:=z+1;
       p:=p div 10;end
               else begin
         y:=0;
      while p<>0 do begin
       y:=y+1;q[y]:=p mod b;
        p:=p div b;
         end;
         for i:=1 to y do
         if q[i]<>0 then break
                    else z:=z+1;end;
        writeln(g,z);end;close(f);close(g);
        end.