using namespace std;
#include<fstream>

int main()
{
	ifstream in("divprim.in");
	ofstream out("divprim.out");
	int N, T, K, ndiv, i, x; 
	in>>T;
	for( ;T>0;T--)
	{	
		in>>N>>K;
		for( ;N && ndiv!=K;N--)
		{
			x=N;i=2;ndiv=0;
			while(x!=1)
			{	
				if(!(x%i))
					ndiv++;
				while(!(x%i))
					x/=i;
				i++;	
			}
			if (ndiv==K)
				out<<N<<'\n';
		}
	if(!N)
		out<<0<<'\n';
	}
	in.close();out.close();
	return 0;
}