#include <stdio.h>

FILE *f,*s;

int i,j,n,x,y,v[1000005],m[1000001][8];

int main()
{
	f=fopen("divprim.in","r");
	s=fopen("divprim.out","w");
	
	for(i=2;i<=1000000;i+=2)
		v[i]++;
	
	for(i=3;i<=1000000;i+=2)
	{
		if(v[i]==0)
		{
			for(j=i;j<=1000000;j+=i)
				v[j]++;
		}	
	}	
	
	for(i=1;i<=1000000;i++)
	{
		for(j=0;j<=7;j++)
			m[i][j]=m[i-1][j];
		
		m[i][v[i]]=i;
	}	
	
	fscanf(f,"%d\n",&n);
	
	for(i=1;i<=n;i++)
	{
		fscanf(f,"%d %d\n",&x,&y);
		
		fprintf(s,"%d\n",m[x][y]);
	}	

	fclose(s);
	
	return 0;
}