#include<bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int n,k;
int maxi,t,a[1000001][8];
short v[1000005];
void f(int k)
{
  int m=0;
  for (int i=2;i<=1000001;i++)
  {
    if (v[i]==k) m=i;
    a[i][k]=m;
  }
}
void ciur()
{
  for (int i=2;i<=1000001;i++)
   {
     if (v[i]==0)
      {
        for (int j=i;j<=1000001;j+=i)
          v[j]++;
      }
   }
}
int main()
{
  fin>>t;
  ciur();
   for (int i=1;i<=7;i++)
     f(i);
   for (int i=0;i<t;i++)
   {
     fin>>n>>k;
     fout<<a[n][k]<<'\n';
   }
   return 0;
}