#include <fstream>
#include <iostream>
#define MAXN 1000001
using namespace std;

int n_div[MAXN];

void ciur()
{
	for(int i = 2; i <= MAXN; ++i)
		if(!n_div[i])
			for(int j = i; j <= MAXN; j += i)
				++n_div[j];
	
}

int main()
{
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	
	int t, n, k;
	
	f >> t;
	
	ciur();
	
	for(int i = 1; i <= t; ++i)
	{
		f >> n >> k;
		
		bool ok = 0;
		
		for(int j = n; j >= 1; --j)
			if(n_div[j] == k)
			{
				g << j << '\n';
				
				ok = 1;
				
				break;
			}
	
	if(!ok)
		g << 0 << '\n';
	}
	
	f.close();
	g.close();
	
	return 0;
}