#include <iostream>
#include <fstream>

using namespace std;

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

int verificPrim(int x)
{
    if(x > 2 && x % 2 == 0 || x <= 1)
    {
        return 0;
    }
    else
    {
        for(int d = 2; d * d <= x; d += 2)
        {
            if(x % d == 0)
            {
                return 0;
            }
        }
    }

    return 1;
}

int main()
{
    int nrTeste, n, nrDivCerut, OK;
    fin >> nrTeste;

   // fout << "cdjvbudvbd";
    for(int i = 0; i < nrTeste; i++)
    {
        fin >> n >> nrDivCerut;
        while(n)
        {
            int d, nr = 0;
            OK = 0;
            for(d = 2; d * d < n; d++)
            {
                if(n % d == 0)
                {
                    if(verificPrim(d) == 1)
                    {
                        nr++;
                    }
                    if(verificPrim(n / d) == 1)
                    {
                        nr++;
                    }
                }
            }
            if(d * d == n && verificPrim(d) == 1)
            {
                nr++;
            }

            if(nr == nrDivCerut)
            {
                fout << n << endl;
                OK = 1;
                break;
            }
            n--;
        }

        if(OK == 0)
        {
            fout << "0" << endl;
        }
    }
    return 0;
}
/*
int ciur[1000009];
    //ciur
    for(int i = 0; i < 1000009; i++)
    {
        ciur[i] = 1;
    }

    ciur[1] = 0;

    for(int d = 2; d * d < 1000009; d++)
    {
        if(ciur[d] == 1)
        {
            for(int i = d * d; d < 1000009; i = i + d)
            {
                ciur[i] = 0;
            }
        }
    }
    //fout << ciur[1];
        /*while(n)
        {
            int d, nr = 0;
            OK = 0;
            for(d = 2; d * d < n; d++)
            {
                if(n % d == 0)
                {
                    if(ciur[d] == 1)
                    {
                        nr++;
                    }
                    if(ciur[n / d] == 1)
                    {
                        nr++;
                    }
                }
            }
            if(d * d == n && ciur[d] == 1)
            {
                nr++;
            }

            if(nr == nrDivCerut)
            {
                fout << n << endl;
                OK = 1;
                break;
            }
            n--;
        }

        if(OK == 0)
        {
            fout << "0" << endl;
        }*/