#include <stdio.h>
#define ma 1000001
using namespace std;
int i,j,n,x,y,d;
int NRD[ma];
int REZ[ma][9];

FILE *f,*g;

void ciur()
{
	for (i=2;i<=ma;++i)
	{
		if (NRD[i]==0)
			for (j=i;j<=ma;j+=i)
				NRD[j]++;
		for (j=1;j<=8;++j)
			REZ[i][j]=REZ[i-1][j];
		REZ[i][NRD[i]]=i;
	}
}

int main()
{
	f=fopen("divprim.in","r");
	g=fopen("divprim.out","w");
	fscanf(f,"%d",&n);
	ciur();
	for (i=1;i<=n;i++)
	{
		fscanf(f,"%d %d",&x,&y);
		fprintf(g,"%d \n",REZ[x][y]);
	}
	fclose(f);
	fclose(g);
	return 0;
}