#include<bits/stdc++.h>
#define NMAX 1000005
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]++;
		}
	}
	V[0].push_back(1);
	for (int i=2; i<=1000000; i++) {	
		if (a[i]<=7) {
			if (!a[i]) V[1].push_back(i);
			else 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;
}