using namespace std;
#include<fstream>
#include<vector>

const int NP=1000005;

int v[NP];

void precalcul()
{
	int i,j;
	for(i=2;i<NP;i+=2)
		++v[i];
	for(i=3;i<NP;i+=2)
		if(!(v[i]))
			for(j=i;j<NP;j+=i)
				v[j]++;
}

inline int nrdiv(int n)
{
	return v[n];
}

int calcul(int n, int k)
{
	for(int i=n;i;--i)
		if (nrdiv(i)==k)
			return i;
	return 0;
}

int main ()
{
	int N,K,T;
	ifstream in("divprim.in");
	ofstream out("divprim.out");
	precalcul();
	in>>T;
	while(T--)
	{	
		in>>N>>K;
		out<<calcul(N,K)<<'\n';
	}
	in.close();out.close();
	return 0;
}