#include<stdio.h>
using namespace std;
#define dim  900000
long v[dim];
int main()
{
	int i,j,n,t,k;
FILE *f=fopen("divprim.in","r"), *g=fopen("divprim.out","w");
fscanf(f,"%d",&t);
for(i=2;i<=dim/2;i++)
	if(v[i]==0)
		{
			for(j=2;j*i<=dim;j++)
			v[i*j]++;
		}

for(i=1;i<=t;i++)
{
	fscanf(f,"%d%d",&n,&k);
	
		for(j=n;j>=1;j--)
		{
			if(v[j]==k) { fprintf(g,"%d\n",j);;break;}
				
		}
		if(j==0)
			fprintf(g,"0\n");


}
fclose(f);
fclose(g);

return 0;}