var n,b,i,j,x,p,nr,aux,c,m:longint;
    f,v:qword;
    a:array[1..10,1..2] of longint;
	k,l:text;
begin
assign(k,'zero2.in');
reset(k);
for i:=1 to 10 do
for j:=1 to 2 do
read(k,a[i,j]);
close(k);
assign(l,'zero2.out');
rewrite(l);
for i:=1 to 10 do  begin
 f:=1;v:=1;
  for x:=1 to a[i,1] do begin
   f:=1;
    for p:=1 to x do
    f:=f*p;
   v:=v*f;
  end;
nr:=0;
aux:=v;
for j:=2 to 2 do
repeat
c:=aux mod a[i,j];
aux:=aux div a[i,j];
if c=0 then nr:=nr+1;
until c<>0;
writeln(l,nr);
end;
close(l);
end.