using namespace std;

#include <iostream>
#include <fstream>
const int N=1000001;
int nrd[N];


void ciur(){
	for(int i=2;i<N;++i)
		if(nrd[i]==0)
			for(int j=i;j<N;j+=i)
				++nrd[j];
}

int maxim(int n, int k)
{
	for(int i=n;i>=1;--i)
		if(nrd[i]==k)
			return i;
	return 0;
}	

int main(){
	int t,n,k,max;
	ciur();
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	f>>t;
	while(t--)
	{
		f>>n>>k;
		/*
		for(int i=2;i<=n;++i)
			if(max<nrd[i] && nrd[i]==k)
				max=nrd[i];
		*/
		g<<maxim(n,k)<<"\n";
	}
	
	f.close();
	g.close();
	return 0;
}