#include<stdio.h>
#define NMAX 1000010
int x[NMAX],n,tt,in,sf,m,i,t,j,k,l,a,s,y[8][NMAX];
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	m=NMAX;
	for (i=2;i<=m;i++)
		if (x[i]==0)
			for (j=i+i;j<=m;j+=i)
				x[j]++;

	for (i=2;i<=m;i++)
		y[x[i]][++y[x[i]][0]]=i;

	for (tt=1;tt<=t;tt++)
	{
		scanf("%d%d",&n,&k);
		in=1;
		sf=y[k][0];
		if (y[k][1]>n)
			printf("0\n");
		else
		{
			while (in<=sf)
			{
				m=(in+sf)/2;
				if (y[k][m]<=n)
					in=m+1;
				else
					sf=m-1;
			}
//			m=(in+sf)/2;
			printf("%d\n",y[k][in-1]);
			}
	}



	return 0;
}