#include<stdio.h>
#include<string>
#define nrmax 1000001
using namespace std;
int max,v[nrmax],mat[nrmax][8];
long int i,j;
void ciur()
{
 for(i=2;i<=nrmax;i++)
    if(v[i]==0)
     {
      for(j=i+i;j<=nrmax;j=j+i)
	     if(v[j]<7)v[j]=v[j]+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 int x,sol,g,k,n;

 scanf("%ld ",&n);

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