#include<cstdio>
#include<vector>
using namespace std;
int a[9][1<<19];
int p[1<<20];
void ciur(int n)
{	
	int i,j;
	for(i=2;i<=n;++i)
	{
		if(p[i]==0)
			for(j=i;j<=n;j+=i)
				p[j]++;
	}
	
	for(i=1;i<=n;++i)
		a[p[i]][++a[p[i]][0]]=i;
	
}	
	
int caut(int p, int k)
{
	int i,pas=1<<19;
	for(i=0;pas;pas>>=1)
		if(i+pas<=a[k][0] && a[k][i+pas]<=p)
			i+=pas;
	if(a[k][i]>p || i==0) return 0;
	return a[k][i];
}
int main()
{
	int t,k,x,y;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	
	scanf("%d",&t);
	ciur(1000000);
	for(k=1;k<=t;++k)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",caut(x,y));
	}
	return 0;
}