#include <cstdio>
#include <string>
#define maxn 1000001

char a[maxn];
char x[maxn][8];

void presolve()
{
	int i, j;
	a[1]=0;
	a[2]=1;
	for(i=4;i<maxn;i+=2) a[i]=1;
	
	for(i=3;i<maxn;i+=2)
		if(!a[i])
			for(j=i;j<maxn;j+=i) ++a[j];

	char ax[8];
	memset(ax, 0, sizeof(0));
	ax[0]=1;
	
	for(i=2;i<maxn;++i)
	{
		memcpy(x[i], ax, sizeof(ax));
		if(a[i]<=7)ax[a[i]]=i;
	}
	
}


int main()
{
	presolve();
	int n,p,q;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d\n", &n);
	//for(scanf("%d\n", &n); n ; --n)
	while(n--)
	{
		scanf("%d %d\n", &p, &q);
		printf("%d\n", x[p][q]);
	}
	
	return 0;
}