#include<stdio.h>
#define nmax 1000010
long n;
int k;
long c[nmax];
long v[8][250010];


void ciur()
{
	long i,j;
	c[1]=0;
	for(i=2;i<=nmax;i++)
		{
			if(c[i]==0)
				for(j=i;j<=nmax;j+=i)
					++c[j];
			v[c[i]][++v[c[i]][0]]=i;
		}
}

long cautare()
{
	long st,dr,m;
	st=1;
	dr=v[k][0];
	while(st!=dr)
	{
		m=(st+dr)>>1;
		if(n<=v[k][m])
			dr=m;
		else
			st=m+1;
	}
	if(v[k][st-1]<=n)
		return v[k][st-1];
	else
		return 0;
}

void read()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	long t;
	scanf("%ld",&t);
	for(;t;t--)
	{
		scanf("%ld",&n);
		scanf("%d",&k);
		printf("%ld\n",cautare());
	}
}

int main()
{
	ciur();
	read();
	return 0;
}