#include<vector>
#include<cstdio>

using namespace std;

const int N = 1<<20;
short int v[N];
int a[8][N];

void gen()
{int i,j;
	v[0]=v[1]=0;
	for (i=2;i<=N;i++)
		if (v[i]==0)
			for (j=i;j<=N;j+=i)
				v[j]++;
	for (i=2;i<=N;i++)
		a[v[i]][++a[v[i]][0]]=i;
}

int cb(int n,int x[],int lung)
{
	int pas=1<<20,i;
	for (i=0;pas;pas>>=1)
		if (i+pas<=lung && x[i+pas]<=n)
			i+=pas;	
	if (x[i]>n||i==0) return 0;
	return x[i];
	
}

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