program gaju;
type tip=0..7;
     tip2=1..100000;
const v:array[1..7]of longint=(2,6,30,210,2310,30030,510510);

var f,g:text;
    n,x,aux,d,i:longint;
    t:tip2;
    k,c:tip;
    found,int:boolean;
begin
assign(f,'divprim.in');
assign(g,'divprim.out');
reset(f);
rewrite(g);
readln(f,t);
for i:=1 to t do begin
    readln(f,n,k);
    if (k<>0) then begin
     found:=false;
    for x:=n downto v[k] do
    if (x mod 2=0)or(x mod 3=0)then begin
        aux:=x;
        c:=0;
        d:=2;
        int:=false;
        while aux<>1 do begin
              while aux mod d=0 do begin
                                aux:=aux div d;
                                if not int then begin
                                        int:=true;
                                        c:=c+1;
                                        end;
                                end;
              d:=d+1;
              int:=false;
              if (d>=x div 2)then begin
                                  c:=c+1;
                                  break;
                                  end;
        end;
        if c=k then begin
                    found:=true;
                    writeln(g,x);
                    break;
                    end;
    end;
    if not found then writeln(g,'0');
    end
    else begin
    found:=false;
    for x:=n downto 1 do begin
        int:=true;
        for d:=2 to trunc(sqrt(x))do if x mod d=0 then begin
                int:=false;
                break;
                end;
        if int then begin
                    found:=true;
                    break;
                    end;
        end;
    if not found then writeln(g,'0')
                 else writeln(g,x);
end;
close(g);
end.