#include<fstream>
#include<iostream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int nrdiv(int n)
{
	int cont = 1;
	int prim = 0;
	while (n % 2 == 0)
	{
		n /= 2;
		cont++;
	}
	if (cont > 1)
	{
		prim++;
	}
	for (int i = 3; i <= n; i += 2)
	{
		int p = 1;
		while (n % i == 0)
		{
			n /= i;
			p++;
		}
		cont *= p;
		if (p > 1)
		{
			prim++;
		}
	}
	if (n > 1)
		cont *= 2;
	return prim;
}

int T, N, K,pass;

int main()
{
	int ok = 0;
	f >> T;
	while (T)
	{
		f >> N >> K;
		while (N)
		{
			if (nrdiv(N) == K)
			{
				g << N << "\n";
				N = 1;
				ok = 1;
			}
			N--;
		}
		if (N == 0 && ok == 0)
		{
			g << ok << "\n";
		}

		T--;
		ok = 0;
	}

	g.close();
	return 0;
}