#include<stdio.h>
#define n 1000000
FILE *fin=fopen("divprim.in", "r");
FILE *fout=fopen("divprim.out", "w");
int k,p,t,i,j,v[1000001][9], a[1000001];
int main()
{
	for (i=2; i<=n; i++)
		if (a[i]==0)
			for (j=i; j<=n; j+=i)
				a[j]++;
	for (i=2; i<=n; i++)
		if (a[i]<=7)
			v[i][a[i]]=i;
	for (i=2; i<=n; i++)
		for (j=1; j<=8; j++)
			if (v[i][j]==0)
				v[i][j]=v[i-1][j];
	fscanf(fin, "%d", &t);
	for (i=1; i<=t; i++)
	{
		fscanf(fin, "%d %d", &p,&k);
		fprintf(fout, "%d\n", v[p][k]);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}