#include <stdio.h>

#define MAX 1000000

long int ciur[MAX], div[MAX];
long int v[MAX];
int m[MAX][10];
long int i, j, k, n;
int p, gasit;
int t, nr;

int main()
{
	FILE *f = fopen ("divprim.in","r");
	FILE *g = fopen ("divprim.out","w");
	fscanf (f,"%d", &t);

	for (i=2; i<=MAX; i+=2)
		v[i] ++;

	for (i=3; i<=MAX; i+=2)
	{
		if (v[i] == 0)
			for( j=i; j<=MAX; j+=i)
				v[j]++;
	}

	for (i=1; i<=MAX; ++i)
	{
		for (j=0;j<=7;j++)
			m[i][j] = m[i-1][j];
		m[i][v[i]] = i;
	}

	for(i=1; i<=t; ++i)
	{
		fscanf(f,"%ld %ld\n", &n, &k);
		fprintf(g,"%d\n", m[n][k]);
	}

	fclose(g);
	fclose(f);
	return 0;
}