#include<vector>
#include<cstdio>

using namespace std;
vector <int> a[8];
const int N = 1<<17;
int v[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]].push_back(i);
}

int cb(int n,vector <int> x,int lung)
{
	int pas=1<<17,i;
	for (i=0;pas;pas>>=1)
		if (i+pas<=lung && x[i+pas]<=n)
			i+=pas;	
	if (x[i]>n) 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].size()));
	}
	
	return 0;
}