using namespace std;

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


void ciur(){
	for(int i=2;i<N;++i)
		if(nrd[i]==0)
			for(int j=i;j<N;j+=i)
				++nrd[j];
	for(int i=1;i<N;++i){
		++a[nrd[i]][0];
		a[nrd[i]][a[nrd[i]][0]]=i;
	}
}
/*
int maxim(int n, int k)
{
	for(int i=n;i>=1;--i)
		if(nrd[i]==k)
			return i;
	return 0;
}
*/

int maxim(int n,int k){//caut binar n pe linia k a matr a
	int u=a[k][0],p=1,m;
	while(p<u)
	{
		m = p + (u-p)/2;
		if(n<=a[k][m])
			u=m;
		else
			p=m+1;
	}
	if(a[k][p]>n)
		--p;
	if(p==0)
		return 0;
	return a[k][p];
}

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;
}