#include <stdio.h>

int a[1000001];
int d[1000001][8];
int i,j,t,x,y;

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",t);
}	for (i=1; i<=500000; i++)
		a[(i<<1)]=1;
	for (i=3; i<=1000000; i++)
		if (!a[i])
			for (j=1; j*i<=1000000; i++)
				a[i*j]++;
	d[1][0]=1;
	for (i=2; i<=1000000; i++){
		for (j=0; j<=7; j++)
			d[i,j]=d[i-1][j];
		d[i,a[i]]=i;
	}
	for (; t; t--){
		scanf("%d %d",&x,&y);
		printf("%d\n",d[x][y]);
	}
	return 0;
}