#include<cstdio>
const int N=1<<20;
int v[N];
int p[10],m[10][N>>1];
void ciur()
{
	int i,j;
	for (i=2;i<N;i++)
	{
		if (v[i]==0)
		{
			for (j=i;j<N;j+=i)
				v[j]++;
		}
	}
}
void matrice()
{
	int i;
	for (i=2;i<N;i++)
		m[v[i]][++p[v[i]]]=i;
}
int cautbin(int a,int b)
{
	int i,pas;
	pas=1<<18;
	for (i=0;pas;pas>>=1)
	{
		if (i+pas<=p[b] && m[b][i+pas]<=a) 
			i+=pas;
	}
	if(i==0)
		return 0;
	return m[b][i];
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int i,t,n,k;
	scanf("%d",&t);
	ciur();
	matrice();
	for (i=1;i<=t;i++)
	{
		scanf("%d %d",&n,&k);
		printf("%d\n",cautbin(n,k));
	}
	return 0;
}