#include<stdio.h>

int v[1000001],m[1000001][8],i,j;
void ciur()
{
 for (i=2; i<=1000000; i++)
   if (v[i]==0)
      for (j=i; j<=1000000; j+=i) v[j]++;
}
void rezolvare()
{
for (i=2; i<=1000000; i++)
 {
   for (j=1; m[i-1][j]>0; j++) m[i][j]=m[i-1][j];
   m[i][v[i]]=i;
 }
}
int main()
  {
  freopen("divprim.in","r",stdin);
  freopen("divprim.out","w",stdout);int n,k,t,i;
   scanf("%d", &t);
   ciur();
   rezolvare();
   for (i=1; i<=t; i++)
     {scanf ("%d %d", &n, &k);
      printf ("%d", m[n][k]);
     }
   return 0;
}