#include <stdio.h>
#include <memory.h>

#define NMAX 1000010

int p[NMAX];
long a[NMAX][8];

void ciur()
{
	long i, j;

	for(j = 2; j < NMAX; j += 2)
		++p[j];

	for(i = 3; i < NMAX; i += 2)
	{
		if(!p[i])
		{
			for(j = i; j < NMAX; j += i)
				++p[j];
		}
		//printf("%ld are %d div primi\n", i, p[i]);
	}
}

void matrix()
{
	long i;
	long until = NMAX;

	a[1][0] = 1;

	for(i = 2; i < until; ++i)
	{
		memcpy(a[i], a[i-1], sizeof(a[i-1]));

		a[i][ p[i] ] = i;
	}
}

void print_a()
{
	int i, j;

	for(i = 1; i < NMAX; ++i)
	{
		for(j = 0; j <= 7; ++j)
		{
			printf("%ld ", a[i][j]);
		}
		printf("\n");
	}
}
int main()
{
	long t, x, y;

	freopen("divprim.in", "r", stdin);
	freopen("divprim.out", "w", stdout);

	ciur();

	matrix();

	//print_a();

	scanf("%ld\n", &t);

	while(t--)
	{
		scanf("%ld %ld\n", &x, &y);

                printf("%ld\n", a[x][y]);

	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}