#include <fstream>
#include <iostream>
using namespace std;
int t,n,k,i,x,s;

void check()
{
	int j,h,g1,g2,cx;
	s=0;
	for (x=n; x>1 && g1==1; x--)
	{
		cx=x;
		for (j=2; j<=cx; j++)
			if (n%j==0)
			{
				g2=1;
				for (h=2; h<=sqrt(j) && g2==1; h++)
					if (j%h==0)
						g2=0;
				if (g2==1)
					s++;
				cx/=j;
			}
		if (s==k)
		{
			g1=0;
			x++;
		}
	}
	if (g1==1)
		x=0;
}

int main()
{
	ifstream inFile("divprim.in");
	ofstream outFile("divprim.out");
	inFile >> t;
	for (i=0; i<t; i++)
	{
		inFile >> n >> k;
		check();
		outFile << x << "\n";
	}
	inFile.close();
	outFile.close();
	return 0;
}