program gaju;
type ve=array[1..100000]of longint;
var s:array[1..100000,0..8]of longint;
    a,b:ve;
    h,t,max:longint;
    f,g:text;
procedure afis;
var i:longint;
begin
for i:=1 to t do writeln(g,s[a[i],b[i]]);
end;
procedure eratos(n:longint);
var v:ve;
    i,j:longint;
begin
fillchar(v,sizeof(v),0);
fillchar(s,sizeof(s),0);
s[1,0]:=1;
i:=2;
while i<=n do begin
      if v[i]=0 then begin
         j:=2*i;v[i]:=1;
         while j<=n do begin
               v[j]:=v[j]+1;
               j:=j+i;
         end;
      end;
      i:=i+1;
end;
for i:=2 to n do begin
         for j:=0 to 8 do s[i,j]:=s[i-1,j];
         s[i,v[i]]:=i;
end;afis;end;
begin
assign(f,'divprim.in');reset(f);
assign(g,'divprim.out');rewrite(g);
readln(f,t);
for h:=1 to t do begin
readln(f,a[h],b[h]);
if max<a[h]then max:=a[h];
end;
eratos(max);
close(g);
end.