#include<stdio.h>
#define NMAX 1000000
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=1000000;
	for (i=2;i<=m;i++)
		if (x[i]==0)
			for (j=i+i;j<=m;j+=i)
				x[j]++;

	for (i=1;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];
		while (in<=sf)
		{
			m=(in+sf)/2;
			if (y[k][m]<=n)
				in=m+1;
			else
				sf=m-1;
		}
		m=(in+sf)/2;
		if (m==0)
			printf("0\n");
		else
			printf("%d\n",y[k][m]);
	}



	return 0;
}