#include<stdio.h>
const int z=1000000;
int t,n,k,nrd[1000000],a[8][z>>1],nrn[8];
void ciur()
{
	int j=0;
	for(int i=2;i<=z;++i)
		if(nrd[i]==0)
			for(j=i;j<=z;j+=i)
				++nrd[j];
	for(int i=1;i<z;++i)
		a[nrd[i]][++nrn[nrd[i]]]=i;
}
int calcul()
{
	// cautare secventiala (lent)
	/*int i=0;
	for(i=n;i;--i)
		if(nrd[i]==k)
			return i;
	return 0;
	*/
	int m=0,s=1,d=nrn[k];
	while(s!=d)
	{
		m=(s+d)/2;
		if(n<=a[k][m])
			d=m;
		else s=m+1;
	}
	if(a[k][s]>n)
		--s;
	return a[k][s];
}
void proba()
{
	/*int i,j;
	for(i=0;i<8;++i)
	{
		printf("%d:",nrn[i]);
		for(j=1;j<100;++j)
			printf("%10d",a[i][j]);
		printf("\n");
	}
	*/
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	ciur();
	proba();
	for(int r=1;r<=t;++r)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",calcul());
	}
	return 0;
}