#include<stdio.h>
int main()
{
	long int i,n,j,a[100],cont=0,p,pp,v[10000],nr,ll;
	long int s=0,k,kk,o,l;
	FILE *in,*out;
	in=fopen("divprim.in","rt");
	out=fopen("divprim.out","wt");
	fscanf(in,"%ld",&nr);
	 for	(ll=1;ll<=nr;ll++)
		{
			fscanf(in,"%ld",&n);
		fscanf(in,"%ld",&k);
	kk=0;
	for (o=1;o<=n;o++)
		{
			pp=1;
			for (l=2;l<=o-1;l++)
			if (o%l==0) pp=0;
			if (pp==1) 	{
						kk=kk+1;
						v[kk]=o;
					}
		}

	for (i=n;i>=1;i--)
		{   cont=0;
		   for (j=2;j<=kk;j++)
			if (i%v[j]==0) cont=cont+1;

		if (k==cont)
					{fprintf(out,"%ld\n",i);
					break;
					}
		}
	if (cont!=k) fprintf(out,"0\n");
	}
}