#include<fstream>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<map>
#include<stack>
#include<cmath>
#include<cstring>
using namespace std;
//#define int long long 
ifstream cin("divprim.in");
ofstream cout("divprim.out");
const int vmax=1e6;
int ciur[vmax+1], ans[vmax+1][8];
void Ciur()
{
    for(int i=2;i<=vmax;i++)
    {
      if(ciur[i]==0)
      {
         for(int j=i;j<=vmax;j+=i)
         {
             ciur[j]++;
         }
      }
    }
}
int main(){
   Ciur();
   int q;
   cin>>q;

   int n, k;
   for(int d=1;d<=7;d++)
   {
      for(int i=1;i<=vmax;i++)
      {
         ans[i][d]=ans[i-1][d];

         if(ciur[i]==d)
         {
            ans[i][d]=max(i, ans[i-1][d]);
         }
      }
   }
   for(int i=1;i<=q;i++)
   {
      cin>>n>>k;
      //cout<<n<<" "<<k<<endl;
      cout<<ans[n][k]<<'\n';
   }

   return 0;
}