#include <fstream>
//#include <iostream>
#define MAX 1000000
using namespace std;
int p[1000099];
int main()
{
   int t,k,n,i,j;
   for(i=2;i<=MAX;i+=2)
        p[i]++;
   for(i=3;i<=1000;i+=2)
    {
        if(p[i]==0)
            for(j=i;j<=MAX;j+=i)
                p[j]++;
    }
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    fin>>t;
    for(i=1;i<=t;i++)
        {
            fin>>n>>k;
            j=n;
            while(p[j]!=k and j>0)j--;
            fout<<j<<"\n";
        }
    fin.close();
    fout.close();
    return 0;
}