#include <stdio.h>
# define N 1000004
int e[N];
int w[1000000] [8];

int main()
{
	int t,n;
	int j,i,k;
	bool b=false;
	FILE *f1,*f2;
	f1=fopen("divprim.in","r");
	f2=fopen("divprim.out","w");
	fscanf(f1,"%d ",&t);
	for(i=1;i<=N-1;i++)
		e[i]=0;
	for(i=2;i<=N-1;i++)
		if(e[i]==0)	
			for(j=i;j<=N-1;j=j+i)	
				e[j]++;
	for(i=2;i<=N-1;i++)
	{
		for(j=1;j<=7;j++)
			w[i] [j]=w[i-1] [j];
		w[i] [e[i]]=i;
	}
	for(i=1;i<=t;i++)
	{
		fscanf(f1,"%d %d",&n,&k);
		fprintf(f2,"%d\n",w[n] [k]);
	}
	fclose(f1);
	fclose(f2);
	return 0;
}