#include<stdio.h>

#define maxN 1000000

FILE*f=fopen("Divprim.in","r");
FILE*g=fopen("Divprim.out","w");

int i,j,n,k,t,p,m,u;
int D[maxN+5],Div[maxN+5],A[8][maxN+5];

inline int cb ( int n , int k ){
	
	p = 1 ; u = A[k][0];
	
	while ( p <= u ){
		m = (p + u) >> 1;
		if ( A[k][m] <= n )
			p = m + 1;
		else
			u = m - 1;
	}
	
	if ( !u )	return 0;
	return A[k][u];
}

int main () {
	
	for ( i = 2 ; i <= maxN ; ++i ){
		if ( !Div[i] ){
			for ( j = i + i ; j <= maxN ; j += i ){
				Div[j] = i;
			}
		}
	}
	
	for ( i = 2 ; i <= maxN ; ++i ){
		if ( !Div[i] ){
			D[i] = 1;
		}
		else{
			if ( (i/Div[i])%Div[i] ){
				D[i] = D[i/Div[i]] + 1;
			}
			else{
				D[i] = D[i/Div[i]];
			}
		}
		if ( D[i] > 7 )	continue ;
		A[D[i]][++A[D[i]][0]] = i;
	}
	
	fscanf(f,"%d",&t);
	
	for ( i = 1 ; i <= t ; ++i ){
		fscanf(f,"%d %d",&n,&k);
		fprintf(g,"%d\n",cb(n,k));
	}
	
	
	
	fclose(f);
	fclose(g);
	
	return 0;
}