#include <stdio.h>
#include <string.h>
#define dim 100

int a[8][dim+1],v[dim+1];
int i,j,n,k;

int main() {
	
  FILE *f = fopen("divprim.in","r");
  FILE *g = fopen("divprim.out","w");
  
  for (i=2; i<=dim; i++) 
	if (v[i]==0)
	  for (j=i; j<=dim; j+=i)
		v[j]++;
  
  for (i=1; i<=7; i++) {
	for (j=1; j<=dim; j++)
      if (v[j]==i)
		a[i][j] = j;
	  else
		a[i][j] = a[i][j-1];
  }
  
  fscanf(f,"%d",&n);
  
  for (k=1; k<=n; k++) {
	fscanf(f,"%d %d",&j,&i);
	fprintf(g,"%d\n",a[i][j]);
  }

  fclose(f);
  fclose(g);  
	
  return 0;
}