// Craciun Catalin 
//  Divprim 
//   Infoarena 
#include <fstream>

#define NMax 1000005

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int n;
int v[1000000];
int a[1000000],mx,m;
int mat[1000000][8];

int main() { 
	
	for(int i=2;i<NMax - 5;i++) {
		if(v[i]==0) {
			a[i]++;
			for(int j=2*i;j<NMax - 5;j+=i) {
				v[j]=1;
				a[j]++;
			} 
		}

		for(int j=1;j<=8;j++)
			mat[i][j]=mat[i-1][j];
		mat[i][a[i]]=i;
	}
 
	int x,div;
 
	for(int j=1;j<=n;j++) {
		f>>x>>div;
		g<<mat[x][div]<<'\n';
	}
 
	return 0;
}