program gaju;
type tip=0..7;
const v:array[1..7]of longint=(2,6,30,210,2310,30030,510510);
var f,g:text;
    n,x,aux,t,d,i:longint;
    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)and(n>1) then begin
     found:=false;
    for x:=n downto v[k] do 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;
                                int:=true;
                                end;
              d:=d+1;
              if int then c:=c+1;
              int:=false;
        end;
        if c=k then begin
                    found:=true;
                    writeln(g,x);
                    break;
                    end;
    end;
    if not found then writeln(g,'0');
    end
    else writeln(g,'0');
end;
close(g);
end.