#include<stdio.h>
#define dim 1000001
using namespace std;

long long v[dim], mat[8][dim];

int main()
{  int K;
   long long T,N,i,j,nr;

	FILE *f = fopen("divprim.in", "r");
	FILE *g = fopen("divprim.out", "w");
	
	fscanf(f, "%lld", &T);
	
	for(i = 2; i <= dim; i++)
		if(v[i] == 0)
			for(j = 1; j <= dim/i; j++)
				v[i*j]++;
					

	for(i = 1; i <= 7; i++)
		{
			nr = 0;
			for(j = 0; j <= dim; j++)
				{
					if(i == v[j]) nr = j;
					mat[i][j] = nr;
				}
		}

		
		
		
		for(i = 1; i <= T; i++)
		{
			N = K = 0;
			fscanf(f, "%lld%d", &N, &K);
			//if(K == 0) {for(j = N; j >= 1; j--) if(v[j] == 0) {fprintf(g, "%lld\n", j); break;}}
			fprintf(g, "%lld\n", mat[K][N]);
		}
	
	fclose(f);
	fclose(g);
	return 0;
}