const m=1000000;
var f1,f2:text; v:array[1..1000000] of integer; i,j,k,t,n,ok:longint;
begin
        assign(f1,'divprim.in');
        reset(f1);
        assign(f2,'divprim.out');
        rewrite(f2);
        read(f1,t);
        for i:=2 to m do begin
                if v[i]=0 then begin
                        j:=0;
                        while j+i<=m do begin
                                j:=j+i;
                                inc(v[j]);
                        end;
                end;
        end;
        for i:=1 to t do begin
                read(f1,n);
                read(f1,k);
                ok:=0;
                if k<>0 then
                        for j:=n downto 1 do begin
                                if v[j]=k then
                                begin
                                        ok:=j;
                                        break;
                                        end; end;
                writeln(f2,ok);
        end;
        close(f1);
        close(f2);
end.