#include <stdio.h>
#include <algorithm>
using namespace std;

const int DIM = 1000005;
int P[10], U[10], T, N, K, R;
struct str1 { int d, i; } ciur[DIM];

int cmp (str1 a, str1 b)
{
	if (a.d != b.d)
		return a.d < b.d;
	return a.i < b.i;
}

void prp_ciur ()
{
	int i, j;
	
	ciur[1].i = 1;
	for (i = 2; i < DIM; i++)
	{
		ciur[i].i = i;
		if (ciur[i].d)
			continue;
		ciur[i].d = 1;
		for (j = i+i; j < DIM; j+=i)
			ciur[j].d++;
	}
	
	sort (ciur, ciur + DIM, cmp);
	
	for (i = 2; i <= DIM; i++)
		if (ciur[i-1].d < ciur[i].d)
			P[ciur[i].d] = i;
	P[8] = DIM;
}

int cauta (int p, int u)
{
	int m;
	while (p <= u)
	{
		m = (p + u) / 2;
		if (ciur[m].i <= N)
			p = m + 1;
		else
			u = m - 1;
	}
	return ciur[u].i;
}

int main ()
{
	freopen ("divprim.in", "r", stdin);
	freopen ("divprim.out", "w", stdout);
	
	prp_ciur();
	
	scanf ("%d", &T);
	while (T--)
	{
		scanf ("%d%d", &N, &K);
		if (K == 0)
			R = 1;
		else if (ciur[P[K]].i > N)
			R = 0;
		else
			R = cauta (P[K], P[K+1] - 1);
		printf ("%d\n", R);
	}
	
	return 0;
}