#include <stdio.h>

long n, i, j, t, o, k, v[1000010], x[8][1000010];

long abs(long a)
{
	return a < 0 ? -a : a;
}

long cautbin(long st, long dr)
{
	long m = (st + dr ) / 2;

	if (x[k][m] == n || abs(st - dr) <= 1)
		return m;
	else
	if (x[k][m] < n)
		return cautbin(m, dr);
	else
		return cautbin(st, m);

}

int main()
{
	freopen ("divprim.in", "rt", stdin);
	freopen ("divprim.out", "wt", stdout);

	for (i = 2; i <= 1000000; ++i)
	{
		if (!v[i])
		{
			v[i] = 1;
			for (j = i + i; j <= 1000000; j += i)
				++v[j];
		}
		x[v[i]][++x[v[i]][0]] = i;
	}

	scanf("%ld", &t);

	for (o = 1; o <= t; ++o)
	{
		scanf("%ld %ld", &n, &k);

		printf("%ld\n", x[k][cautbin(1, x[k][0])] <= n ? x[k][cautbin(1, x[k][0])] : 0);
	}
	return 0;
}