#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] = 1;
        }
}

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

    Eratosthenes();
    for(i = 1; i < MAXN; ++i)
    {
        if(!m[i])
        {
            ++a[0], A[1][ a[0] ] = i;
            continue;
        }
        aux = i;
        if(i == 30)
            i = i;
        nr = 0;
        for(j = 1; v[j] * v[j] <= aux && aux > 1; ++j)
            if(aux % v[j] == 0)
            {
                ++nr;
                while(aux % v[j] == 0)
                    aux /= v[j];
            }
        if(aux > 1)
            ++nr;
        ++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;
}