#include <stdio.h>

long d[1000001],m[1000001][8],n,k,i,j,t;

void ciur ()  {

	long i,j;
	for(i=2;i<=1000000;i+=2)
		++d[i];
	for(i=3;i<=1000000;i++)
		if(d[i]==0)
			for(j=i;j<=1000000;j+=i)
				++d[j];
}

int main () {

	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);

	ciur();

	for(i=2;i<=1000000;i++){
		for(j=0;j<=8;j++){
			m[i][j]=m[i-1][j];
		}
        m[i][d[i]]=i;
    }
	
	
	scanf("%ld",&t);

	for(i=1;i<=t;i++)
	{
		scanf("%ld%ld",&n,&k);
		printf("%ld\n",m[n][k]);
	}
	return 0;
}