#include <stdio.h>
#define NMAX 1000000
#define QMAX 100000

FILE *f = fopen("divprim.in","rt"), *g = fopen("divprim.out","wt");

long int query[QMAX][2],n,i,j,k,pr[NMAX],div[NMAX],T,sol[NMAX][8];


void citire()
{
fscanf(f,"%ld",&T);
n=0;
for (i=1;i<=T;i++)
	{fscanf(f,"%ld %ld",&query[i][0],&query[i][1]);
	if (query[i][0]>n) n=query[i][0];}
}


void solve()
{
for (i=1;i<=n;i++)
	{pr[i]=1;div[i]=0;}
for (i=2;i<=n;i++)
	if (pr[i]) {div[i]=1;
		    k=2*i;
		    while (k<=n)
			{pr[k]=0;
			div[k]++;
			k+=i;
			}
		    }
for (i=1;i<=n;i++)
	{
	for (j=1;j<=7;j++)
		sol[i][j]=sol[i-1][j];
	sol[i][div[i]]=i;
	}

for (i=1;i<=T;i++)
	fprintf(g,"%ld\n",sol[query[i][0]][query[i][1]]);
}





int main()
{
citire();
solve();
fclose(f);
fclose(g);
return 0;
}