/// gliga paul
/// cn grigore moisil
/// casa a 10 a
/// [email protected]
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprimi.in");
ofstream g("divprimi.out");
int main()
{
    int t,k,i,j,d,s,ok,m;
    long n;
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>n>>k;
        s=0;
        for(j=n;j<=2;j--)
        {
            ok=1;
            if(j%2==0)
                s++;
                for(d=3;d<j;d=d+2)
                {
                   for(m=3;m*m<=d;m=m+2)
                    {
                        if(d%m==0)
                            ok=0;
                    }
                if(ok==1)
                    s++;
                }
             if(s==k)
                g<<j<<endl;
        }
    }


    return 0;
}