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

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

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

	FILE *f = fopen("divprim.in", "r");
	FILE *g = fopen("divprim.out", "w");
	
	fscanf(f, "%d", &T);
	
	for(i = 3; i*i <= dim; i+=2)
		if(v[i] == 0)
			for(j = i+i; j <= dim; j+=i)
				v[j]++;
					
	
	for(i = 3; i <= dim; i++)
		{
			if(i % 2 == 0) v[i]++;
			if(v[i] == 1) mat[1][i] = i, mat[2][i] = mat[2][i-1], mat[3][i] = mat[3][i-1], mat[4][i] = mat[4][i-1], mat[5][i] = mat[5][i-1], mat[6][i] = mat[6][i-1], mat[7][i] = mat[7][i-1];
				else if(v[i] == 2) mat[2][i] = i, mat[1][i] = mat[1][i-1], mat[3][i] = mat[3][i-1], mat[4][i] = mat[4][i-1], mat[5][i] = mat[5][i-1], mat[6][i] = mat[6][i-1], mat[7][i] = mat[7][i-1];	
				else if(v[i] == 3) mat[3][i] = i, mat[1][i] = mat[1][i-1], mat[2][i] = mat[2][i-1], mat[4][i] = mat[4][i-1], mat[5][i] = mat[5][i-1], mat[6][i] = mat[6][i-1], mat[7][i] = mat[7][i-1];	
				else if(v[i] == 4) mat[4][i] = i, mat[1][i] = mat[1][i-1], mat[2][i] = mat[2][i-1], mat[3][i] = mat[3][i-1], mat[5][i] = mat[5][i-1], mat[6][i] = mat[6][i-1], mat[7][i] = mat[7][i-1];	
				else if(v[i] == 5) mat[5][i] = i, mat[1][i] = mat[1][i-1], mat[2][i] = mat[2][i-1], mat[3][i] = mat[3][i-1], mat[4][i] = mat[4][i-1], mat[6][i] = mat[6][i-1], mat[7][i] = mat[7][i-1];	
				else if(v[i] == 6) mat[6][i] = i, mat[1][i] = mat[1][i-1], mat[2][i] = mat[2][i-1], mat[3][i] = mat[3][i-1], mat[4][i] = mat[4][i-1], mat[5][i] = mat[5][i-1], mat[7][i] = mat[7][i-1];	
				else if(v[i] == 7) mat[7][i] = i, mat[1][i] = mat[1][i-1], mat[2][i] = mat[2][i-1], mat[3][i] = mat[3][i-1], mat[4][i] = mat[4][i-1], mat[5][i] = mat[5][i-1], mat[6][i] = mat[6][i-1];	
				else mat[1][i] = mat[1][i-1], mat[2][i] = mat[2][i-1], mat[3][i] = mat[3][i-1], mat[4][i] = mat[4][i-1], mat[5][i] = mat[5][i-1], mat[6][i] = mat[6][i-1], mat[7][i] = mat[7][i-1];
		}
		
		
		
		for(i = 1; i <= T; i++)
		{
			N = K = 0;
			fscanf(f, "%d%d", &N, &K);
			fprintf(g, "%d\n", mat[K][N]);
		}
	
	fclose(f);
	fclose(g);
	return 0;
}