#include<fstream>

using namespace std;

#define MAXN 1000002
#define MAXK 9

int T, N, K, i, j, nr;
int m[ MAXN ];
int A[ MAXN ][ MAXK ];

inline void Eratosthenes()
{
    int i, j;

    for(i = 2; i < MAXN; i += 2)
        m[i] = 1;
    for(i = 3; i < MAXN; ++i)
        if(!m[i])
        {
            for(j = 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] << '\n';

        --T;
    }

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

    return 0;
}