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.
Y29uc3QgICBmaT0nJzsKICAgICAgICBmbz0nJzsKICAgICAgICBvbz0zMDAwMDAwOwp2YXIgICAgIGssdCxpLGosdHQ6bG9uZ2ludDsKICAgICAgICB0YW0sbixyZXM6cXdvcmQ7CiAgICAgICAgZjp0ZXh0OwogICAgICAgIHRtcDphcnJheVsyLi5vb10gb2YgYm9vbGVhbjsKICAgICAgICBuZ3RvOmFycmF5WzEuLm9vXSBvZiBsb25naW50OwogICAgICAgIGQJOmxvbmdpbnQ7CmZ1bmN0aW9uIG1heChhLGI6cXdvcmQpOnF3b3JkOwpiZWdpbgogICAgICAgIGlmIGE+YiB0aGVuIGV4aXQoYSkgZWxzZSBleGl0KGIpOwplbmQ7CnByb2NlZHVyZSB4bDsKdmFyICAgICBpLGogOmxvbmdpbnQ7CmJlZ2luCglmb3IgaTo9MSB0byBkLWsrMSBkbwoJCWJlZ2luCgkJCXRhbSA6PTE7CgkJCWZvciBqOj1pIHRvIGkray0xIGRvCgkJCWJlZ2luCgkJCQl0YW0gOj0gdGFtKm5ndG9bal07CgkJCWVuZDsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgdGFtPm4gdGhlbiBicmVhayBlbHNlIHJlcyA6PSBtYXgocmVzLHRhbSk7CgkJZW5kOwplbmQ7CnByb2NlZHVyZSBpbml0OwpiZWdpbgogICAgICAgIGZvciBpOj0yIHRvIHRydW5jKHNxcnQob28pKSBkbwogICAgICAgICAgICAgICAgaWYgdG1wW2ldPWZhbHNlIHRoZW4KICAgICAgICAgICAgICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGo6PWkqaTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHdoaWxlIGo8PW9vIGRvCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdG1wW2pdOj10cnVlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBqOj1qK2k7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgICAgICAgICBlbmQ7CiAgICAgICAgZDo9MDsKICAgICAgICBmb3IgaTo9MiB0byBvbyBkbwogICAgICAgICAgICAgICAgaWYgdG1wW2ldPWZhbHNlIHRoZW4gYmVnaW4gaW5jKGQpOyBuZ3RvW2RdOj1pOyBlbmQ7CiAgICAgICAgajo9ZDsKZW5kOwpwcm9jZWR1cmUgbmhhcDsKYmVnaW4KICAgIGFzc2lnbihmLGZpKTtyZXNldChmKTsKICAgIGFzc2lnbihvdXRwdXQsZm8pO3Jld3JpdGUob3V0cHV0KTsKICAgIHJlYWQoZix0KTsKICAgIGZvciB0dDo9MSB0byB0IGRvCiAgICAgICAgYmVnaW4KICAgICAgICAgICAgcmVhZChmLG4sayk7CiAgICAgICAgICAgIHJlcyA6PSAwOwogICAgICAgICAgICB4bDsKICAgICAgICAgICAgaWYgcmVzPTAgdGhlbiB3cml0ZWxuKC0xKSBlbHNlIHdyaXRlbG4ocmVzKTsKICAgICAgICBlbmQ7CiAgICBjbG9zZShmKTtjbG9zZShvdXRwdXQpOwplbmQ7CmJlZ2luCiAgICBpbml0OwogICAgbmhhcDsKZW5kLg==