#include <bits/stdc++.h>

using namespace std;

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

int n, k, t, st, dr, mid, v[1000100];
vector <int> s[8];

void bs(int n, int k){
	st = 0; dr = s[k].size() - 1;
	if(n < s[k][st]){
		out << "0\n";
		return;
	}
	while(st <= dr){
		mid = (st + dr) / 2;
		if(s[k][mid] <= n) st = mid + 1;
		else dr = mid - 1;
	}
	out << s[k][dr] << '\n';
}

int main(){
	in >> t;
	for(int i = 2; i <= 1000000; i++)
		if(!v[i])
			for(int j = i; j <= 1000000; j += i) v[j]++;
	for(int i = 1; i <= 1000000; i++)
		if(v[i] <= 7) s[v[i]].push_back(i); 
	while(t--){
		in >> n >> k;
		bs(n, k);
	}	
	return 0;
}