#include<stdio.h>
using namespace std;
#define MAX 1000005

FILE *f=fopen("divprim.in","r"), *g=fopen("divprim.out","w");

int phi[MAX],sol[MAX][8];

int main ()
{
	int i,j;
	for(i=3;i<=MAX;i+=2)
	{
		if(phi[i]==0)
		{
            phi[i]=1;
			for(j=2*i;j<=MAX;j+=i)
				phi[j]++;
		}
		phi[i+1]++;
	}
	for(i=1;i<=MAX;i++)
	{
		for(j=0;j<=7;j++)
 			sol[i][j]=sol[i-1][j];
		sol[i][phi[i]]=i;
	}
	int T;
	fscanf(f,"%d",&T);
	while(T--)
	{
		fscanf(f,"%d %d",&i,&j);
		fprintf(g,"%d\n",sol[i][j]);
		
	}
fclose(f);
fclose(g);
return 0;
}