#include <fstream>
using namespace std;
int cr[1000001],y,v[8][1000001],temp[8][1000001],m;
int main() {
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int i,j,t,k,p;
	for (i=2; i<=1000000; i++)
		if (!cr[i]) {
			j=1; 
			while (i*j<=1000000) {
				cr[i*j]+=1;
				j++;
			}
		}
	for (i=2; i<=1000000; i++) {
		for (j=0; j<=7; j++)
			v[j][i]=v[j][i-1];
		if (cr[i]<=7)
			v[cr[i]][i]=i;
	}
		
		
/*	for (i=2; i<=1000000; i++) {
		temp[cr[i]][0]++;
		temp[cr[i]][temp[cr[i]][0]]=i;
	}
	for (i=0; i<=7; i++) {
		m=0;
		for (j=1; j<=1000000; j++) {
			if (temp[i][m+1]<=j) {
				m++;
				v[i][j]=temp[i][m];
			}
			else if (m)
					v[i][j]=temp[i][m];
			else v[i][j]=0;
		}
	}*/
	f>>t;
	for (i=1; i<=t; i++) {
		f>>p>>k;
		g<<v[k][p]<<'\n';
	}		
	g.close();
	return 0;
}