var t,n,k,p,i,j:longint;
    v:array[1..50000] of byte;
    f,g:text;
    ok:boolean;
begin
assign (f,'divprim.in');
assign (g,'divprim.out');
reset (f);
rewrite (g);
read (f,t);
for i:=1 to t do
    begin
    read (f,n,k);
    for j:=1 to n do
        v[j]:=0;
    for j:=2 to n do
        begin
         if v[j]=0 then
            for p:=j to n do
                if p mod j=0 then v[p]:=v[p]+1;
        end;
    ok:=false;
    for j:=n downto 2 do
        if (v[j]=k) and (ok=false) then
            begin
             writeln (g,j);
             ok:=true;
            end;
    if ok=false then writeln (g,'0');
    end;
close (f);
close (g);
end.