#include<bits/stdc++.h>
#define f first 
#define s second
#define NMAX 1000050
using namespace std;

int t,a[1000100];
vector<int>V[10];
vector<int>::iterator it;

int main() {
	ifstream cin("divprim.in");
	ofstream cout("divprim.out");
	cin>>t;
	for (int i=2; i<=sqrt(NMAX); i++) {
		if (!a[i]) for (int j=i; j<=NMAX; j+=i) {
			a[j]++;
		}
	}
	for (int i=1; i<=NMAX; i++) {
		if (a[i]<=7) V[a[i]].push_back(i);
	}
	for (int i=0; i<=7; i++) sort(V[i].begin(),V[i].end());
	
	while (t--) {
		int n,k;
		cin>>n>>k;
		it= upper_bound(V[k].begin(), V[k].end(),n);
		if (it!=V[k].begin()) cout<<*(it-1)<<'\n';
		else cout<<0<<'\n';
	}
	
	return 0;
}