program pz;
var  f,g:text;i,n,j,b,y,z,a,k:longint;p:real;
     q:array[1..65000]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:=trunc(p)*k;
      for j:=1 to i do
       p:=trunc(p)*j; end;
      if b=10  then
       while trunc(p) mod 10=0 do begin
       z:=z+1;
       p:=trunc(p) div 10;end
               else begin
         y:=0;
      while trunc(p)<>0 do begin
       y:=y+1;q[y]:=trunc(p) mod b;
        p:=trunc(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.