#include<fstream>
#include<vector>

using namespace std;

#define MAXN 1000002
#define MAXK 9

int T, N, K, i, j, nr, st, mid, end;
int m[ MAXN ], v[ MAXN ], a[ MAXK ];
int A[ MAXN ][ MAXK ];

inline void Eratosthenes()
{
    int i, j;

    v[0] = 1;
    v[1] = 2;
    m[1] = 1;
    i = 4;
    while(i < MAXN)
        m[i] = 1, i += 2;
    for(i = 3; i < MAXN; i += 2)
        if(!m[i])
        {
            ++v[0], v[ v[0] ] = i;
            for(j = i + i; j < MAXN; j += i)
                ++m[j];
        }
}

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

    Eratosthenes();
    for(i = 1; i < MAXN; ++i)
    {
        for(j = 0; j <= 8; ++j)
            A[i][j] = A[i-1][j];
        A[i][ m[i] ] = i;
    }

    f >> T;
    while(T)
    {
        f >> N >> K;

        g << A[N][K] << endl;

        --T;
    }

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

    return 0;
}