#include <stdio.h>
#define N 1000005
#define M 400000
char c[N];
void ciur (){
	c[1]=1;
	for (int i=2; i<N; i++){
		if (!c[i])
			for (int j=i; j<N; j+=i)
				c[j]++;
	}
}
int a[8][M];
void matrice (){
	for (int i=1; i<N; i++){
		a[c[i]][++a[c[i]][0]]=i;
	}
}
int f (int v[M], int x)
{
	int m, p=1, u=v[0];
	while (u!=p){
		m=(p+u)/2;
		if (x<=v[m])
			u=m;
		else
			p=m+1;
	}
	if (v[p]>x)
		--p;
	if(p==0)
		return 0;
	return v[p];
}
int main ()
{
	int t, n, k, i,;
	freopen ("divprim.in", "r", stdin);
	freopen ("divprim.out", "w", stdout);
	ciur();
	matrice();
	scanf ("%d", &t);
	for (i=1; i<=t; i++){
		scanf ("%d%d", &n, &k);
		printf ("%d\n", f(a[k], n));
	}
	return 0;
}