#include <stdio.h>
int d[1000001], m[1000001][10];
void ciur ()
{
	int i,j;
	for(i=2;i<=1000000;i=i+2)
		d[i]++;
	for(i=3;i<=1000000;i++)
		if(d[i]==0) 
			for(j=i;j<=1000000;j=j+i)
				d[j]++;
}
int main() 
{
	int i,j,n,k,t;
	freopen("divprim.in","r", stdin);
	freopen("divprim.out","w", stdout);
	ciur();
	for(i=2;i<=1000001;i++)
	{
		for(j=0;j<8;j++)
			m[i][j]=m[i-1][j];
		m[i][d[i]]=i;
	}
	scanf("%d",&t);
	for(i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",m[n][k]);
	}
	return 0;
}