program pz;
var  f,g:text;i,n,j,b,x,z,p,q,a,k:longint;
     v: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:=1;k:=1;z:=0;x:=0;
     for i:=2 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
          q:=1;
      while p<>0 do begin
        q:=q*10+p mod b;
        p:=p div b;
         end;
       while q div 10<>0 do begin
        x:=x+1;v[x]:=q mod 10;
          q:=q div 10;end;
          while v[x]=0 do begin
        x:=x-1;z:=z+1;end;end;
        writeln(g,z);end;close(f);close(g);
        end.