#include<cstdio>

const int N = (1<<20);
const int K = (1<<3);

int a[K][N],nrd[N];

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

void calcul_mat()
{
	int i,j;
	for(i=1;i<N;++i)
		a[nrd[i]][i]=i;
	for(i=0;i<K;++i)
		for(j=1;j<N;++j)
			if(a[i][j]==0)
				a[i][j]=a[i][j-1];
}

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	ciur();
	calcul_mat();
	int t,n,k;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",a[k][n]);
	}
	return 0;
}