#include<stdio.h>
#define nmax 1000010
long n;
int k;
int c[nmax+2];
long long v[9][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 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]==n)
		return v[k][st];
	if(v[k][st-1]==n)
		return v[k][st-1];
	if(v[k][st+1]==n)
		return v[k][st+1];
	if(st==0)
		if(v[k][st+1]<=n)
			return v[k][st+1];
		else
			return 0;
	if(st==1)
		return v[k][st];
	else
		return v[k][st-1];
}

int exista(int x)
{
	long prod=1;
	long prime[]={0,2,3,5,7,11,13,17,19};
	for(;x;x--)
		prod=prod*prime[x];
	return prod<=n;
}

void read()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	long t;
	int i;
	scanf("%ld",&t);
	for(i=1;i<=7;i++)
	{
		v[i][++v[i][0]]=999999999;
	}
	for(;t;t--)
	{
		scanf("%ld",&n);
		scanf("%d",&k);
		if(k!=0)
		{
			if(exista(k))
				printf("%lld\n",cautare());
			else
				printf("0\n");
		}
		else
			printf("1\n");
	}
}

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