#include <fstream>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
bool c[1000001];
int divi[500000];
int ind = 1;

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

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

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

            ct = 0;
            for(y = 1; y <= ind; y++)
            {
                if(j % divi[y] == 0)
                {
                    ct++;
                    if(ct > k)
                        break;
                }
            }
            if(ct == k)
            {
                fout << j;
                ok = 1;
                fout << "\n";
                break;
            }
        }
        if(ok == 0)
        {
            fout << 0;
            fout << "\n";
        }
    }



    return 0;
}