#include <stdio.h>
# define N 1000004
int e[N];

int main()
{
	int t,n;
	int j,i,k;
	bool b=false;
	FILE *f1,*f2;
	f1=fopen("divprim.in","r");
	f2=fopen("divprim.out","w");
	fscanf(f1,"%d ",&t);
	for(i=1;i<=N-1;i++)
		e[i]=0;
	for(i=2;i<=N-1;i++)
		if(e[i]==0)	
			for(j=i;j<=N-1;j=j+i)	
				e[j]++;

	for(i=1;i<=t;i++)
	{
		b=false;
		fscanf(f1,"%d %d",&n,&k);
		for(j=n;j>=1;j--)
			if(e[j]==k)
			{
				fprintf(f2,"%d\n",j);
				b=true;
				break;
			}
		if(!b)	fprintf(f2,"%d\n",0);
	}
	fclose(f1);
	fclose(f2);
	return 0;
}