#include <stdio.h>
#define maxl 1000004



using namespace std;
FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");

int cr[maxl],a[maxl][9],i,j,t,n,k;

void ciur()
{
 int i,j;
 for(i=2;i<=maxl;i++)
 if (cr[i]==0)
 for(j=i;j<=maxl;j+=i)
 cr[j]++;
}



int main()
{
ciur();
for(i=2;i<=1000000;i++)
{
 for(j=0;j<=7;j++)
  a[i][j]=a[i-1][j];

a[i][cr[i]]=i;
}
fscanf(f,"%d",&t);
for(i=1;i<=t;i++)
{
fscanf(f,"%d%d",&n,&k);
fprintf(g,"%d\n",a[n][k]);
}
fclose(g);
return 0;
}