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



void generez()
{
  for(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;
 }