#include <cstdio>
#include <cmath>
int v[1000005];
int L7A2 (int n)
{
	int i, e = 0, nr = 0;
	while (n % 2 == 0)
		e ++, n /= 2;
	i = 3;
	if (e > 0)
		nr ++;
	int q = (int) sqrt ((double) n);
	while (i <= q)
	{
		e = 0;
		
		while (n % i == 0)
			n /= i, e ++;
		
		if (e > 0)
			nr ++;
		
		i += 2;
	}
	if (n > 1)
		nr ++;
	
	return nr;
}
int main()
{
	freopen ("divprim.in", "r", stdin);
	freopen ("divprim.out", "w", stdout);
	int t, o, max = 0;
	scanf ("%d", &t);
	int i;
	for (i = 2; i <= 1000000; i ++)
	{
		v[i] = L7A2 (i);
		if (max < v[i])
			max = v[i];

	}
	for (o = 1; o <= t; o ++)
	{
		int n, k;
		scanf ("%d%d", &n, &k);
		
		{
			int j = n;
			for (; j >= 1; j --)
				if (v[j] == k)
				{
					printf ("%d\n", j);
					break;
				}
			if (j == 0)
				printf ("0\n");
		}
	}
	return 0;
}