lotus.eater086

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<iomanip>
#include<cmath>
#include<bitset>

#define LL long long
#define endl "\n"

using namespace std ;

//
template < typename T >

inline T read( T &x )
{

    x = 0 ;

    int f = 0 ;

    char ch = getchar() ;

    while( ch < '0' || ch > '9' )  {

        f |= ( ch == '-' ) , ch = getchar() ;

    }

    while( ch >= '0' && ch <= '9' )  {

        x = ( x << 1 ) + ( x << 3 ) + ch - '0' , ch = getchar() ;

    }

    return x = f ? -x:x ;

}
//

vector<LL> v ;

const LL MOD = 1e10 ;

LL power( LL x , LL y)
{
    LL res = 1LL ;

    while ( y > 0) {

        if (y & 1)
            res = res * x ;


        y = y >> 1 ;

        x = x * x ;

    }

    return res ;

}

void precalculate( void )
{

    for( LL i = 0 ; i <= 31 ; i++ )  {  // 2

        for( LL j = 0 ; j <= 19 ; j++ )  {  // 3

            for( LL a = 0 ; a <= 12 ; a++ )  {  // 5

                for( LL b = 0 ; b <= 11 ; b++ )  {  // 7

                    LL x1 , x2 , x3 ;

                    LL xyz = 1e9 ;

                    x1 = ( ( power(2,i)  )*( power(3,j) ) )  ;

                    if( x1 > xyz )  continue ;

                    x2 = (  (  power(5,a)  )*(   power(7,b)   ) ) ;

                    if( x2 > MOD )  continue ;

                    x3 = (  (x1 )*(  x2   )   )  ;

                    if( x3  > xyz )  continue ;

                    else v.emplace_back( x3 ) ;

                }

            }

        }

    }

    sort( v.begin() , v.end() ) ;

}

LL bs( LL key )  // binary search
{

    LL low = 0 , high = v.size() - 1 , ans = -1 ;

    while( low <= high )  {

        LL mid = low + ( high - low )/2 ;

        if( v[mid] == key )  {

            return key ;

        }

        else if( v[mid] > key )  {

            ans = v[mid] ;

            high = mid-1 ;

        }

        else  {

            low = mid+1 ;

        }

    }

    return ans ;

}

void solve( void )
{

    precalculate() ;     // making numbers in global vector using 2,3,5,7

    int t ;

    read( t ) ;

    while( t-- )  {

        LL n ;

        read( n ) ;

        LL output = bs( n ) ;

        printf( "%lld\n", output ) ;

    }

}

int main( void )

{

    //ios_base::sync_with_stdio( false ) ;  cin.tie( NULL ) ;  cout.tie( NULL ) ;

    #ifndef ONLINE_JUDGE
        freopen( "input.txt" , "r" , stdin ) ;
        freopen( "output.txt" , "w" , stdout ) ;
    #endif

    if( 0 )  {

        int t = 100 ;

        for( int i = 1 ; i <= t ; i++ )  solve() ;

    }

    else  {

        solve() ;

    }

    #ifndef ONLINE_JUDGE
        cout << "\nTime Elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << " sec\n" ;
   #endif

    return 0 ;

}