#include<stdio.h>
const int N = 1<<20;
int a[8][1<<20],v[1<<20],x[1<<20],t,n,k;
int amireprost(int x,int v[N])
{
	int i,pas=1<<19;
	for (i=0;pas!=0;pas>>=1)
		if(i+pas<=v[0] && v[i+pas]<=x)
			i+=pas;
	if(i==0) return 0;
	else return v[i];
}
void ciurul_lui_nu_stiu_cine()
{
	int i,j;
	for(i=2;i<N;++i)
		if(x[i]==0)
			for(j=i;j<N;j+=i)
				++x[j];
}
void vrajeli()
{
	int i;
	for(i=1;i<N;++i)
		a[ x[i] ] [ ++ a[x[i]][0]]=i;
}
int main()
{
	int i;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	ciurul_lui_nu_stiu_cine();
	vrajeli();
	for(i=1;i<=t;++i)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",amireprost(n,a[k]));
	}
	return 0;
}