#include<stdio.h>

long long ok[1000000];
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<=1000000;i++)
		if(!ok[i])
		{	j=2;
			while(i*j<=1000000)
			{	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");}
		for(y=n;y>=2;y--)
		{	j=2;x=0;
			while(j<=y/2)
			{	if(!ok[j]&&y%j==0) x++;
				if(x>k) break;
				j++;
			}
			if(x==k) break;
		}
		if(k==x&&y>=2)
		{	fprintf(g,"%ld",y);
			fprintf(g,"\n");
		}
		else { fprintf(g,"0");fprintf(g,"\n");}
	}
	return 0;
}