#include <cstdio>
#include <cstring>
#define max 1000009;
int main()
{int j,n,i,k,t,v[1000009],a[8][1000009];
 
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
 
 a[0][0]=1;a[0][1]=1;
 for (i=1;i<=7;i++) a[i][0]=0;
 memset(v,0,sizeof(v));
 
 a[1][0]=2;a[1][1]=2;a[1][2]=3;
 
 for (i=4;i<=100001;i++)
 {if (i%2==0) v[i]++;
  if (i%3==0) v[i]++;
  if (v[i]==0) for (j=i;j<=1000;j+=i) v[j]++;
  a[v[i]][0]++;a[v[i]][a[v[i]][0]]=i;
 }
 
 scanf("%d",&t);
 for (i=1;i<=t;i++)
 {scanf("%d %d",&n,&k);
  if (a[k][1]>n) printf("0\n"); else
  {for (j=1;j<=a[k][0];j++) 
	  if ((a[k][j+1]>n) || (j==a[k][0]))
	  {printf("%d\n",a[k][j]);
	   break;
	  }
  }
 }
 /*for (i=0;i<=8;i++)
 {for (j=1;j<=a[i][0];j++)
	 printf("%d ",a[i][j]);
 printf("\n");
 }*/
 return 0;
}