#include <stdio.h>

int main()
{
	int t,n,k,l,d;
	long long j,i;
	bool e[1000004];
	bool b;
	b=false;
	FILE *f1,*f2;
	f1=fopen("divprim.in","r");
	f2=fopen("divprim.out","w");
	fscanf(f1,"%d ",&t);
	for(i=1;i<=1000003;i++)
	{
		e[i]=false;
	}
	for(i=2;i<=1000003;i++)
	{
		if(e[i]==false)	for(j=i*i;j<=1000003;j=j+i)	e[j]=true;
	}
	for(i=1;i<=t;i++)
	{
		fscanf(f1,"%d %d",&n,&k);
		if(k>=1)
			{
			for(j=n;j>=2;j--)
			{
				b=false;
				if(e[j]==true)
				{	d=0;
					for(l=2;l<=n;l++)
					{
						if(e[l]==false && j%l==0)	d=d+1;
					}
				}
				if(d==k)	
				{
					fprintf(f2,"%d\n",j);
					b=true;
					break;
				}
			}
				if(b==false)	fprintf(f2,"%d\n",0);
			}
		
		if(k==0)	fprintf(f2,"%d\n",1);
	}
	fclose(f1);
	fclose(f2);
	return 0;
}