#include<stdio.h>
#include<math.h>
long *v=new long[1000001];
int main()
{long n,i,j,t,x,p,k,r;
v[1]=0; v[2]=0; v[3]=0;
j=1;
while(2*j<=1000000) {v[2*j]++;j++;}
for(i=3;i<=(long)sqrt(1000000);i+=2)
	{
	if (v[i]==0)
		{
		j=1;
		while(i*j<=1000000)
			{v[i*j]++;
			j++;}
		}

	}
FILE*f=fopen("divprim.in","r");
FILE*g=fopen("divprim.out","w");
fscanf(f,"%ld",&t);
for(i=1;i<=t;i++)
	{
	fscanf(f,"%ld %ld",&n,&k);
	for(j=n;j>=1;j--)
		{
		if (v[j]==k) {fprintf(g,"%ld\n",j);
		break;}}
	 if (j==0) fprintf(g,"0\n");
	}
fclose(g);
return 0;}