#include<stdio.h>
#include<algorithm>

using namespace std;

#define nmax 1000010
long n;
int k;
int c[nmax+2];
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 cautare()
{
	return *lower_bound(v[k] + 1, v[k] + v[k][0], n);
	long st,dr,m;
	st=1;
	dr=v[k][0];
	while(st!=dr)
	{
		m=(st+dr+1)>>1;
		if(v[k][m] <= n)
			dr=m-1;
		else
			st=m;
	}
	return v[k][st];
}

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]]=0;
	}
	for(;t;t--)
	{
		scanf("%ld",&n);
		scanf("%d",&k);
		if(k!=0)
		{
			if(exista(k))
				printf("%ld\n",cautare());
			else
				printf("0\n");
		}
		else
			printf("1\n");
	}
}

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