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

int v[dim];

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

	FILE *f = fopen("divprim.in", "r");
	FILE *g = fopen("divprim.out", "w");
	
	fscanf(f, "%lld", &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 = 1; i <= T; i++)
		{
			fscanf(f, "%lld%d", &N, &K);
			for(j = N; j >= 1; j--)
				if(j % 2 == 0)
				  {if(v[j]+1 == K) 
					{fprintf(g, "%lld\n", j); break;}}
				  else {if(v[j] == K) 
						  {fprintf(g, "%lld\n", j); break;}}
				 
			if(j == 0) fprintf(g, "0\n");
		}
	
	fclose(f);
	fclose(g);
	return 0;
}