#include<stdio.h>
int main()
{long n,i,j,v[1000001],t,x,p,k,r;
v[1]=0; v[2]=0; v[3]=0;
for(i=4;i<=1000001;i++)
	{
	k=0;
	if(i%2==0) r=1;
	else r=2;
	for(j=i-r;j>=3;j-=2)
		{
		if (v[j]==0&&i%j==0) k++;
		}
	if(i%2==0) k++;
	v[i]=k;
	}
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 (j==1) fprintf(g,"0\n");
	}
fclose(f);
fclose(g);
return 0;}