var
a,b:array[1..10010] of longint;
f,ff:array[2..10010] of boolean;
n,i,j,z:longint;
max:int64;
jieguo:array[1..10010] of char;
function fen(x:longint):longint;
var
i,l:longint;
begin
for i:=2 to x div 2 do
if x mod i=0 then begin
f[i]:=true;
x:=x div i;
end;
end;
function gcd(x,y:longint):longint;
begin
if y=0 then gcd:=x
else gcd:=gcd(y,x mod y);
end;
begin
readln(n);
for i:=1 to n do begin
fillchar(f,sizeof(f),0);
read(a[i],b[i]);
z:=gcd(a[i],b[i]);
a[i]:=a[i] div z;
b[i]:=b[i] div z;
fen(b[i]);
for j:=2 to 10010 do
ff[j]:=ff[j] or f[j];
end;
max:=1;
for i:=2 to 10010 do
if ff[i] then max:=max*i;
i:=0;
while max>0 do begin
inc(i);
z:=max mod 16;
max:=max div 16;
if z>9 then jieguo[i]:=chr(z+55)
else jieguo[i]:=chr(z+48);
end;
for j:=i downto 1 do
write(jieguo[j]);
writeln;
end.