#include <fstream>
#include <iostream>
using namespace std;
int t,n,k,i,x,s,j,h,g1,g2,v[9592];

int main()
{
	v[0]=2; v[1]=3; g2=2;
	for (i=5; i<=99991; i+=2)
	{
		g1=1;
		for (j=2; j<=i/2 && g1==1; j++)
			if (i%j==0)
				g1=0;
		if (g1==1)
		{
			v[g2]=i;
			g2++;
		}
	}
	ifstream inFile("divprim.in");
	ofstream outFile("divprim.out");
	inFile >> t;
	for (i=0; i<t; i++)
	{
		inFile >> n >> k;
		g1=1;
		for (x=n; x>1 && g1==1; x--)
		{
			s=0;
			for (j=0; v[j]<=x; j++)
				if (x%v[j]==0)
					s++;
			if (s==k)
			{
				g1=0;
				x++;
			}
		}
		if (g1==1)
			x=0;
		outFile << x << "\n";
	}
	inFile.close();
	outFile.close();
	return 0;
}