#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;
for(i=2;i<=(long)sqrt(1000001);i++)
	{
	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>=2;j--)
		{
		if (v[j]==k) {fprintf(g,"%ld\n",j);
		break;}}
	if (k==0) fprintf(g,"1\n");
	else if (j==1) fprintf(g,"0\n");
	}
fclose(g);
return 0;}