#include<fstream>
using namespace std;
int main()
{
	int T,K,N,s,j,pus,k;
	ifstream yu("divprim.in");
	ofstream uy("divprim.out");
	yu>>T;
	while (T--)
	{
		yu>>N>>K;
		while (N--)
		{
			s=0; k=0;
			pus=N;
			for (j=2;j*j<=N;j++)
			{
				if (pus%j==0) s+=1;
				while (pus%j==0) pus/=j;
			}
			if (pus!=1) s+=1;
			if (s==K) { uy<<N<<"\n"; k=1; break; }
		}
		if (k==0) uy<<"0\n";
	}
	return 0;
}