#include<fstream>
#include<vector>

using namespace std;

#define MAXN 1000002
#define MAXK 9

int T, N, K, i, j, nr, aux, st, mid, end;
char m[ MAXN ];
int v[ MAXN ];
int A[ MAXK ][ MAXN ], a[ 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])
        {
            if(i >= 950000)
                i = 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)
    {
        nr = m[i];
        ++a[nr], A[nr][ a[nr] ] = i;
    }

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

        i = st = 1, end = a[K];
        while(st <= end)
        {
            mid = (st + end) / 2;
            if(A[K][mid] <= N)
                i = mid, st = mid + 1;
            else end = mid - 1;
        }
        if(A[K][i] > N)
            --i;

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

        --T;
    }

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

    return 0;
}