// http://infoarena.ro/problema/divprim


#include<stdio.h>
#include<math.h>

#define DIM 1000001

int v[DIM];


void ciur()
{
	for(int i=2;i<=1000;i++)
		if(v[i]==0)
			for(int j=i+i;j<=DIM;j+=i)
				v[j]++;
}


int main()
{
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	int t,k;
	scanf("%ld",&t);
	ciur();
	long int j,n;
	for(long int i=1;i<=t;i++)
	{
		scanf("%ld %ld",&n,&k);
		for( j=n;j>=1;j--)
			if(v[j]==k) {printf("%ld\n",j);break;}
		if(j==0) printf("%ld\n",0);
	}
}