program p1;
 var
     m,i,a,b,k,j:longint;

 function cmmdc(a,b:longint):longint;
  begin
   if a mod b=0 then cmmdc:=b
    else cmmdc:=cmmdc(b,a mod b);
  end;

 begin
   assign(input,'pinex.in');
   reset(input);
   assign(output,'pinex.out');
   rewrite(output);
   readln(m);
   i:=1;
   for i:=1 to m do
    begin
     readln(a,b);
     k:=0;
     for j:=1 to a do if cmmdc(b,j)=1 then inc(k);
     writeln(k);
    end;
   close(output);
 end.