#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];
	//a[i][0]=nr cu i div
	//a[i][1]....a[i][a[a[i]a[0]]] care sunt div
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;
	freopen ("divprim.in","r",stdin);
	freopen ("divprim.out","w",stdout);
	ciur();
	matrice();
	scanf ("%d",&t);
	for(;t;--t){
		scanf ("%d%d",&n,&k);
		printf("%d\n",f(a[k],n));
	}
	return 0;
}