var a,b:array[1..500]of longint;
    v:boolean;
    n,i,j,x,p:integer;
    f,g:text;
procedure prim(x,y:longint);
var aux:longint;
begin
while y<>0 do
begin
aux:=x mod y;
x:=y;
y:=aux;
end;
if x=1 then v:=true
        else v:=false;
end;


begin
assign(f,'pinex.in');reset(f);
assign(g,'pinex.out');rewrite(g);
readln(f,n);
for i:=1 to n do
readln(f,a[i],b[i]);
for i:=1 to n do
 begin
 for x:=2 to a[i] do
 begin
 prim(x,b[i]);
 if v=true then p:=p+1;
 end;
 writeln(g,p+1);p:=0;
 end;
 close(f); close(g);
end.