#include <fstream>
using namespace std;
ifstream fi("divprim.in");
ofstream fo("divprim.out");
const int Dim=1000000;

int t,n,k,a[Dim+1],i,j,ok;
int pr[]={2,3,5,7,11,13,17};

int main()
{
for(i=0;i<=6;i++)
for (j=pr[i];j<=Dim;j+=pr[i]) a[j]+=1;

fi>>t;

 for(i=1;i<=t;i++)
 {fi>>n>>k;
  ok=1;
  for(j=n;j>=0;j--)
     if(a[j]==k) {fo<<j<<'\n';ok=0;break;}
  if(ok==1) fo<<"0"<<'\n';
 }


    return 0;
}