#include <cstdio>

const int M=1000000;


long int a[M][10],v[M],i,j,k,n,t,nr;

void citire()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
}
void ciur()
{
	for(i=2;i<=M;i+=2)
		v[i]++;
	for (i=3;i<=M;i+=2)
	{
		if(v[i]==0)
			for(j=i;j<=M;j+=i)
				v[j]++;
	}
	for (i=1;i<=M;++i)
	{
		for (j=0;j<=7;j++)
			a[i][j]=a[i-1][j];
		a[i][v[i]]=i;
	}
}
void work()
{
	for(i=1; i<=t; ++i)
	{
		scanf("%ld%ld",&n, &k);
		printf("%d\n",a[n][k]);
	}
}
int main()
{
	citire();
	ciur();
	work();
	return 0;
}