#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;


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;
			}
		    }
div[1]=0;
for (i=1;i<=T;i++)
	{k=query[i][1];
	j=query[i][0];
	while (div[j]!=k&&j>0)
		j--;
	fprintf(g,"%ld\n",j);
	}
}





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