const m=1000000;
var f1,f2:text; v:array[1..1000000] of integer; i,j,k,t,n,ok:longint; a:array[0..1000000,0..8] of 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 m do begin
                a[i]:=a[i-1];
                a[i,v[i]]:=i;
        end;
        for i:=1 to t do begin
                read(f1,n);
                read(f1,k);
                writeln(f2,a[n,k]);
        end;
        close(f1);
        close(f2);
end.