program fainnaspa;
var f,g:text;
    i,n,k,t:longint;

procedure rez(n,k:longint);
var i,j,max:longint;
    v:array[1..1000010]of integer;
begin
fillchar(v,n,0);
i:=2;max:=-1;
while (i<=n) do begin
      if v[i]=0 then begin
         j:=i*2;
      while (j<=n) do begin
                inc(v[j]);
                j:=j+i;
      end;
      end;
     if (max<i)and(v[i]=k)then max:=i;
     i:=i+1;
end;
if max<>-1 then writeln(g,max)
           else writeln(g,0);
end;

begin
assign(f,'divprim.in');reset(f);
assign(g,'divprim.out');rewrite(g);
readln(f,t);

for i:=1 to t do begin
         readln(f,n,k);
         rez(n,k);
end;

close(f);close(g);

end.