#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int t, n, k;

/// c[i] --> daca numarul i este prim sau nu
bool c[1000001];

///  d[i] --> cati divizori primi are numarul i
int d[1000001];

int M[8][1000000];

int main()
{
    int i, j;
    c[2] = 1;
    for(i = 3 ; i <= 1000000; i += 2)
        c[i] = 1;

    for(i = 2; i <= 1000000; i += 2)
        d[i]++;

    for(i = 3; i <= 1000000; i += 2)
        if(c[i] == 1)
        {
            d[i] = 1;
            for(j = 2 * i; j <= 1000000; j += i)
            {
                c[j] = 0;
                d[j]++;
            }
        }

    for(i = 2; i <= 1000000; i++)
        if(d[i] <= 7)
            M[ d[i] ][ ++M[d[i]][0] ] = i;

    fin >> t;
    for(i = 1; i <= t; i++)
    {
        fin >> n >> k;

        int st = 1, dr = M[k][0], rasp;
        if(n < M[k][1])
            fout << 0 << "\n";
        else
        {
            while(st <= dr)
            {
                int mij = (st + dr) / 2;
                if(M[k][mij] <= n)
                    {
                        rasp = M[k][mij];
                        st = mij + 1;
                    }
                else
                {
                    dr = mij - 1;
                }
            }
            fout << rasp << "\n";
        }
    }
    return 0;
}