var f,g:text;n,b,y,k,d,l,c,i:longint;
function fact(x:longint):longint;
var p:longint;j:byte;
begin
p:=1;
for j:=2 to x do p:=p*j;
fact:=p;
end;
begin
assign(f,'zero2.in');reset(f);assign(g,'zero2.out');rewrite(g);
for l:=1 to 8 do begin read(f,n,b);c:=0;d:=1;
for i:=2 to n do
d:=d*fact(i);y:=0;k:=0;
repeat y:=y*10+d mod b;d:=d div b;until d=0;
repeat k:=k*10+y mod 10;y:=y div 10;until y=0;
while k mod 10=0 do begin k:=k div 10;inc(c);end;writeln(g,c);end;
close(g);close(f);end.