#include<stdio.h>
#define ELFMAX 1000000 + 1
int c[ELFMAX],din[8][ELFMAX];
inline void ciuruit()
{
int i,j;
for(i=2;i<ELFMAX;i++)
  if(!c[i])
    {
    for(j=(i<<1);j<ELFMAX;j+=i)
      c[j]++;
    c[i]++;
    }
} //s-a gandit cineva sa pregenereze ciuru?


int main()
{
int i,j,t,val1,val2;
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
ciuruit();
for(i=1;i<ELFMAX;i++)
 din[0][i]=1;
for(i=1;i<=7;i++)
  for(j=1;j<ELFMAX;j++)
    {
    if(c[j]==i)
      din[i][j]=j;
    else
      din[i][j]=din[i][j-1];
    }
scanf("%d",&t);
for(i=1;i<=t;i++)
  {
  scanf("%d%d",&val2,&val1);
  printf("%d\n",din[val1][val2]);
  }
return 0;
}