#include<stdio.h>
#include<string>
#define nrmax 1000001
using namespace std;
long  max,v[nrmax],mat[nrmax][8];
long long i,j;
void ciur()
{
 for(i=2;i<=nrmax;i++)
    if(v[i]==0)
     {
      for(j=i;j<=nrmax;j=j+i)
	     if(v[j+i]<=7)v[j+i]=v[j+i]+1;

      }



 }
void generez()
{
  for(int i=2; i<=nrmax; i++)
  {
    memcpy(mat[i],mat[i-1], sizeof mat[i]);
    
    mat[i][v[i]] = i;
  }
}

int main()
{
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);

 ciur();
 generez();
 long long g,k,n;

 scanf("%lld ",&n);

 for(i=1;i<=n;i++)
  {
   scanf("%lld %lld",&g,&k);
   printf("%ld\n",mat[g][k]);
   }
 return 0;
 }