#include <fstream>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
bool c[1000001];

void Ciur()
{
    c[2] = 1;
    for(int x = 3; x <= 1000001; x += 2)
        c[x] = 1;

    for(int x = 3; x * x <= 1000001; x += 2)
        if(c[x] == 1)
            for(int j = x * x; j <= 1000001; j += 2 * x)
                c[j] = 0;
}

int main()
{
    int t, n, k, i, j, div, ct, ok ;
    fin >> t;
    Ciur();
    for(i = 1; i <= t; i++)
    {
        fin >> n >> k;
        ok = 0;
        for(j = n; j >= 1; j--)
        {

            ct = 0;
            for(div = 2; div <= j; div++)
            {
                if(c[div] == 1 && j % div == 0)
                    ct++;
            }
            if(ct == k)
            {
                fout << j;
                ok = 1;
                fout << "\n";
                break;
            }
        }
        if(ok == 0)
        {
            fout << 0;
            fout << "\n";
        }
    }



    return 0;
}