#include<stdio.h>
#define NN 1000007

int nrd[NN];

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

int calcul(int N,int K)
{
	int i;
	for( i=N ; i ; --i )
		if( nrd[i] == K )
			return i;
	return 0;
}

int main()
{
	//Declaratii
	int T,K,N;
	
	// Citire
	freopen ("divprim.in","r",stdin) ;
	freopen ("divprim.out","w",stdout) ;
	scanf ("%d",&T) ;
	ciur();
	//Rezolvare
	while (T--)
	{
		scanf("%d%d",&N,&K);
		printf("%d\n",calcul(N,K));
	}
	return 0;
}