const f = 'divprim.in'; g = 'divprim.out';


var
    prim : array[0..1000000] of longint;
    sol : array[0..1000000,0..8] of longint;
    t, k, n, m, i, j : longint;
begin
    assign( input,f ); reset( input );
    assign( output,g ); rewrite( output );
    readln( t );

    for i := 2 to 1000000 do begin
        if prim[i] = 0 then begin
            inc( prim[i] );
            j := i + i;
            while j <= 1000000 do begin
                inc( prim[j] );
                j := j + i;
            end;
        end;
    end;
    for i := 1 to 1000000 do begin
        sol[i] := sol[i-1];
        sol[i][prim[i]] :=i;
    end;

    while t > 0 do begin
        readln( n , k );
        writeln( sol[n][k] );
        dec( t );
    end;

end.