#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
bool prim(int x)
{
	for (int i = 2; i <= sqrt(x); i++)
	{
		if (x % i == 0)
		{
			return false;
		}
	}
	return true;
}
int omega(int x)
{
	if (x == 1)
		return 0;
	else
	{
		int s = 0;
		for (int i = 2; i <= x; i++)
		{
			if (prim(i))
			{
				if (x % i == 0)
					s++;
			}
		}
		return s;
	}
}
int main()
{
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	int T, N, K;
	fin >> T;
	for (int i = 1; i <= T; i++)
	{
		fin >> N >> K;
		for (int j = N; j >=1; j--)
		{
			if (omega(j) == K)
			{
				fout << j << endl;
				break;
			}
			if (j == 1)
				fout << 0 << endl;
		}
	}
}