program gaju;
type ve=array[1..1000000]of longint;
var s:array[0..8]of longint;
    k:byte;
    h,n,t:longint;
    f,g:text;
procedure eratos;
var v:ve;
    i,j:int64;
begin
fillchar(v,sizeof(v),0);
fillchar(s,sizeof(s),0);
s[0]:=1;
i:=2;
while i<=n do begin
      if v[i]=0 then begin
         v[i]:=1;
         j:=2*i;
         while j<=n do begin
               v[j]:=v[j]+1;
               j:=j+i;
         end;end;
      if s[v[i]]<i then s[v[i]]:=i;
      i:=i+1;
end;
writeln(g,s[k])
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,n,k);
eratos;
end;
close(g);
end.