const max=;

 var u,c,p:array[..max] of longint;

     g:array[..max] of int64;

     v:array[..max] of boolean;

     i,j,t,n,m:longint;

 function min(a,b:longint):longint;

   begin

     if a>b then exit(b) else exit(a);

   end;

 function cal(n,m:longint):int64;

   var i,j:longint;

   begin

     i:=;

     cal:=;

     while i<=min(n,m) do

     begin

       j:=min(n div (n div i), m div (m div i));

       cal:=cal+int64(u[j]-u[i-])*g[n div i]*g[m div i];

       i:=j+;

     end;

   end;

 begin

   u[]:=;

   g[]:=;

   c[]:=;

   for i:= to max do

   begin

     if not v[i] then

     begin

       inc(t);

       p[t]:=i;

       g[i]:=;

       c[i]:=;

       u[i]:=-;

     end;

     for j:= to t do

     begin

       if i*p[j]>max then break;

       v[i*p[j]]:=true;

       if i mod p[j]= then

       begin

         g[i*p[j]]:=g[i] div (c[i]+)*int64(c[i]+);

         c[i*p[j]]:=c[i]+;

         u[i*p[j]]:=;

         break;

       end;

       g[i*p[j]]:=g[i]*;

       u[i*p[j]]:=-u[i];

       c[i*p[j]]:=;

     end;

   end;

   for i:= to max do

   begin

     u[i]:=u[i-]+u[i];

     g[i]:=g[i-]+g[i];

   end;

   readln(t);

   while t> do

   begin

     dec(t);

     readln(n,m);

     writeln(cal(n,m));

   end;

 end.