#include <stdio.h>
#define max 1000000
#define D 1000010

int p[D],N,K,T,i,j;

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

	scanf("%d",&T);

	for(i=1;2*i<=max;i++)
		p[i*2]=1;
	for(i=3;i*i<=max;i+=2)
		if(p[i]==0)
			for(j=i;j<=max;j+=i)
				p[j]++;

	for(i=1;i<=T;i++)
	{
		scanf("%d%d",&N,&K);
		p[0]=K;
		while(N>=0)
		{
			if(p[N]==K)
			{
				printf("%d\n",N);
				break;
			}
			N--;
		}
	}

	return 0;
}