#include <fstream>

using namespace std;
int p[100003];
int main()
{
   int t,k,n,i,j;
   for(i=2;i<=100000;i+=2)
        p[i]++;
   for(i=3;i<=1000000;i+=2)
    {
        if(p[i]==0)
            for(j=i;j<=1000000;j+=2*i)
                p[j]++;
    }
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    fin>>t;
        for(i=1;i<=t;i++)
        {
            fin>>n>>k;
            while(p[n]!=k)
                n--;
            fout<<n<<"\n";
        }
    fin.close();
    fout.close();
    return 0;
}