#include <iostream>
#include <fstream>

using namespace std;

#define Nmax 1000007
#define Kmax 8

int ciur[Nmax];
int dp[Nmax][Kmax];

void gen()
{
    for ( int i = 2; i < Nmax; ++i )
            if ( !ciur[i] )
                    for ( int j = i; j < Nmax; j += i )
                            ciur[j]++;
}

void calc()
{
    for ( int i = 2; i < Nmax; ++i )
    {
        for ( int j = 1; j < Kmax; ++j )
                dp[i][j] = dp[i - 1][j];

        dp[i][ ciur[i] ] = i;
    }
}

int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");

    int T, N, K;

    gen();
    calc();

    for ( f >> T; T; T-- )
    {
        f >> N >> K;

        g << dp[N][K] << "\n";
    }

    f.close();
    g.close();

    return 0;
}