using namespace std;
#include<fstream>

const int NP=1<<20;

int v[NP],a[8][NP>>1];

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]++;
	for(i=1;i<NP;++i)
		a[v[i]][ ++a[v[i]][0] ]=i;
}


int calcul(int n, int k)
{
	int p=1,u=a[k][0],m;
	while(p!=u)
	{
		m=(p+u)/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 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;
}