// Craciun Catalin
//  Divprim
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

#define NMax 1000005

int div[NMax];
vector<int> M[8];

void ciur() {
	
	memset(div, 0, sizeof(div));
	for (int i=2;i<=1000000;i+=2)
		div[i] = 1;
	for (int i=3;i<=1000000;i+=2) {
		if (div[i]==0) {
			for (int j=i;j<=1000000;j+=i)
				div[i]++;
		}
	}
	
	for (int i=1;i<=1000000;i++) {
		if (div[i] <= 7)
			M[div[i]].push_back(i);
	}
}

int caut(int x, int d) {
	
	int toRet = 0;
	int st = 0, dr = M[d].size() - 1;
	
	while (st <= dr) {
		int mij = (st + dr)/2;
		if (M[d][mij] == x)
			return x;
		else if (M[d][mij] > x) {
			dr = mij - 1;
		} else if (M[d][mij] < x) {
			toRet = M[d][mij];
			st = mij + 1;
		}
	}
	
	return toRet;
}

int n;
int main() {
	
	ciur();
	f>>n;
	for (int i=1;i<=n;i++) {
		int x, d;
		f>>x>>d;
		g<<caut(x,d)<<'\n';
	}

	f.close();
	g.close();
	
	return 0;
}