#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int t = 0;
	f >> t;
	struct treaba{
		int first, second;
		vector<int>::iterator it; };

	vector<treaba> v(t);
	vector<int> rezultate(t);

	auto it = begin(rezultate);

	for(auto& x : v){
		f >> x.first >> x.second;
		x.it = (it++); }

	sort(begin(v), end(v), [](const treaba& lhs, const treaba& rhs){
		return lhs.first < rhs.first; });

	vector<int> nr_div_prim(v.back().first+1, 0);

	int rez[8] = {1, 0}, i = 1;
	for(const auto x : v){
		for( ; i <= x.first; ++i){
			if(i > 1 && nr_div_prim[i] == 0){
				for(unsigned long long j = i; j < nr_div_prim.size(); j += i){
					++nr_div_prim[j]; } }
			rez[nr_div_prim[i]] = i; }
		*(x.it) = rez[x.second]; }
	for(const auto x : rezultate){
		g << x << '\n'; }
	return 0; }