const fi=''; fo=''; oo=3000000; var k,t,i,j,tt:longint; tam,n,res:qword; f:text; tmp:array[2..oo] of boolean; ngto:array[1..oo] of longint; d :longint; function max(a,b:qword):qword; begin if a>b then exit(a) else exit(b); end; procedure xl; var i,j :longint; begin for i:=1 to d-k+1 do begin tam :=1; for j:=i to i+k-1 do begin tam := tam*ngto[j]; end; if tam>n then break else res := max(res,tam); end; end; procedure init; begin for i:=2 to trunc(sqrt(oo)) do if tmp[i]=false then begin j:=i*i; while j<=oo do begin tmp[j]:=true; j:=j+i; end; end; d:=0; for i:=2 to oo do if tmp[i]=false then begin inc(d); ngto[d]:=i; end; j:=d; end; procedure nhap; begin assign(f,fi);reset(f); assign(output,fo);rewrite(output); read(f,t); for tt:=1 to t do begin read(f,n,k); res := 0; xl; if res=0 then writeln(-1) else writeln(res); end; close(f);close(output); end; begin init; nhap; end.