#include<stdio.h>
#define NN 1000007

int nrd[NN],a[8][NN>>1],nrn[8];

void ciur()
{
	int i,j;
	for(i=2;i<NN;++i)
		if(nrd[i]==0)
			for(j=i;j<NN;j+=i)
				++nrd[j];
	for(i=1;i<NN;++i)
		a[nrd[i]][++nrn[nrd[i]]]=i;
}

int calcul(int N,int K)
{
	//cautare secventiala (lent)
	/*
	int i;
	for( i=N ; i ; --i )
		if( nrd[i] == K )
			return i;

	return 0;
	*/
	//cautare binara ( FC Rapid Bucuresti ):
	int s=1,d=nrn[K],m;
	while(s!=d)
	{
		m=(s+d)/2;
		if(N<=a[K][m])
			d=m;
		else
			s=m+1;
	}
	if(a[K][s]>N)
		s--;
	return a[K][s];
}
/*
void proba()
{
	int i,j;
	for(i=0;i<8;++i)
	{
		printf("%d: ",nrn[i]);
		for(j=1;j<100;++j)
			printf("%10d",a[i][j]);
		printf("\n");
	}
}
*/
int main()
{
	//Declaratii
	int T,K,N;
	
	// Citire
	freopen ("divprim.in","r",stdin) ;
	freopen ("divprim.out","w",stdout) ;
	scanf ("%d",&T) ;
	ciur();
	//proba();
	//Rezolvare
	while (T--)
	{
		scanf("%d%d",&N,&K);
		printf("%d\n",calcul(N,K));
	}
	return 0;
}