/*
Nume: Lazar Vlad-Eduard
Scoala: Colegiul "Nicolae Titulescu", a-X-a A
Email: [email protected]
*/
#include <fstream>

using namespace std;

int main()
{
    ifstream f("divprim.in");
    ofstream fout("divprim.out");
    int i,n,k,t,mx=2,m,j,ok;
    f>>t;
    for (i=0;i<t;i++)
    {
        ok=0;
        f>>n>>k;
        for (j=n;j>=3;j--)
        {
            int r=0;
            for (m=3;m<j;m+=2)
            {
                if (j%m==0)
                {
                    int div=0;
                    for (int d=3;d<m;d++)
                        if (m%d==0) div++;
                    if (div==0) {r++;}
                }
            }
            if (j%2==0) r++;
            if (r==k) {ok=1;fout<<j<<endl; break;}
        }
        if (ok==0) fout<<0<<endl;
    }
    return 0;
}