#include<cstdio>
#include<vector>

using namespace std ;
const int NMAX = 1<<20 ;

vector<int> a[8] ;

short int  v [ NMAX ] ;

void preg ( )
{
	int i , j ;
	for ( i = 2 ; i <= NMAX ; i ++ )
		if ( v[i] == 0 )
			for ( j = i ; j <= NMAX ; j += i )
				v[j] ++ ;
	for ( i = 2 ; i <= NMAX ; i ++ )
		a [ v[i] ] . push_back ( i ) ;
}

int caut ( int val , vector<int> x , int n  )
{
	int pas = 1 << 19 , i ;
	for ( i = 0 ; pas ; pas >>=1 )
		if ( i+pas <= n && x[i+pas] <= val )
			i+= pas ;
	if ( x[i] > val ) return 0 ;
	return x[i] ;
}

int main ( ) 
{
	freopen ( "divprim.in" , "r" , stdin ) ;
	freopen ( "divprim.out" , "w" , stdout ) ;
	
	int T , n , k , i ;
	
	scanf ( "%d" , & T ) ;
	preg ( ) ;
	for ( i = 1 ; i <= T ; i ++ )
	{
		scanf ( "%d%d" , & n , & k ) ;
		int lim = a[k].size ();
		printf ( "%d\n" , caut ( n , a[k] , lim ) ) ;
	}
	
	return 0 ;
}