#include <fstream>
#include <iostream>
#include <utility>
using namespace std;

int get_treaba(const int x, const int y){
	static int nr_div[1000001] = {0},
		calc_pana_la = 1,
		rez[1000001][8] = { {0}, {1, 0} };
	for(int i = calc_pana_la+1; i <= x; ++i){
		if(nr_div[i] == 0){
			for(long int j = 2*i; j <= 1000000; j += i){
				++nr_div[j]; } }
		for(long int j = 0; j < 8; ++j){
			rez[i][j] = rez[i-1][j]; }
		rez[i][nr_div[i]] = i; }
	calc_pana_la = max(calc_pana_la, x);
	return rez[x][y]; }

int main(){
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int t = 0;
	f >> t;
	get_treaba(10000, 10);
	for(int i = 0, n, k; i < t; ++i){
		f >> n >> k;
		g << get_treaba(n, k) << '\n'; }
	return 0; }