#include<stdio.h>

long long ok[10000];
long k,x,n,t,i,j,y,prim;

int main()
{	FILE*f=fopen("divprim.in","r");
	FILE*g=fopen("divprim.out","w");
	for(i=2;i*i<=10000;i++)
		if(!ok[i])
		{	j=2;
			while(i*j<=10000)
			{	ok[i*j]=1;
				j++;
			}
		}
	fscanf(f,"%ld",&t);
	for(i=1;i<=t;i++)
	{	fscanf(f,"%ld",&n);
		fscanf(f,"%ld",&k);
		if(k==1&&!ok[n]) {fprintf(g,"%ld",n);fprintf(g,"\n");}
		else
		{	for(y=n;y>=5;y--)
			{	j=2;x=0;
				if(k==1&&!ok[y]) {fprintf(g,"%ld",n);fprintf(g,"\n");break;}
				while(j<=y/2)
				{	if(!ok[j]&&y%j==0) x++;
					if(x>k) break;
					j++;
				}
				if(x==k) break;
			}
			if(k==x)
			{	fprintf(g,"%ld",y);
				fprintf(g,"\n");
			}
			else { fprintf(g,"0");fprintf(g,"\n");}
		}
	}
	return 0;
}