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