#include<cstdio>

const int N=1000000;
int d[N],a[8][N],n,k,t,nr[8];
void ciur()
{
	int i,j;
	for(i=2;i<N;++i)
    {
        if(d[i]==0)
           for(j=i;j<N;j+=i)
               ++d[j];
    }
}
void constr()
{
	int i;
	ciur();
	for(i=1;i<N;++i)
		a[d[i]][++ nr[d[i]] ] = i;
}
int cautbin(int k,int n)
{
	int i,pas=1<<20;
	for(i=0;pas!=0;pas/=2)
	{
		if(i+pas<=nr[k] && a[k][pas+i]<=n)
			i+=pas;
	}
	return a[k][i];
}

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