const max=1000000;

var a:array[1..max] of integer;
    d:array[1..max,0..7] of longint;
    f,g:text;
    n,x,y,i,j:longint;
begin
 assign(f,'divprim.in'); reset(f);
 assign(g,'divprim.out'); rewrite(g);
 for i:=1 to max shr 1 do
  a[i shl 1]:=1;
 for i:=3 to max do
  if a[i]=0 then
   for j:=1 to max div i do
    inc(a[i*j]);
 d[1,0]:=1;
 for i:=2 to max do begin
  for j:=0 to 7 do
   d[i,j]:=d[i-1,j];
  d[i,a[i]]:=i;
 end;
 read(f,n);
 for i:=1 to n do begin
  read(f,x,y);
  writeln(g,d[x,y]);
 end;
 close(f); close(g);
end.