#include<cstdio>

const int N=1<<20;
const int M=1<<3;
const int K=1<<19;

int p[N],nr[M],a[M][K];

void ciur()
{
	for (int i=2;i<N;i++)
		if (p[i]==0)
			for (int j=i;j<N;j+=i)
				p[j]++;
}

int cautbin(int n,int k)
{
	int i=0,pas=K;
	for (;pas;pas>>=1)
		if (i+pas<=nr[k] && a[k][i+pas]<=n)
			i+=pas;
	return a[k][i];
}

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	ciur();
	for (int i=1;i<N;i++)
	{
		nr[p[i]]++;
		a[p[i]][nr[p[i]]]=i;
	}
	int t,n,k;
	scanf("%d",&t);
	for (int i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",cautbin(n,k));
	}
	return 0;
}