#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

#include<math.h>

using namespace std;

long long int ll=1e9;

long long int ss[];

/*

long long int pow(long long int a, long long int b)

 {

    long long int ans = 1;

     while(b)

     {

         if(b & 1)ans *= a;

        a *= a;

         b>>=1;

     }

     return ans;

 }*/

 ///不定义上面这个函数的话答案就是错误的

因为对于pow在文件中定义的函数的返回值类型是double，而本题仅仅要求返回long long类型的值，若是直接用文件中自定义的pow函数就会因为精度的差异而造成错误

int main()

{

    int t;

  long long int ch;

    cin>>t;

    while(t--){

            int p=;

        int n;

        for(long long int i=;i<;i++)

        for(long long int j=;j<;j++)

            for(long long int k=;k<;k++)

        for(long long int l=;l<;l++){

            ch=pow(,i)*pow(,j);

            if(ch>ll)break;

            ch*=pow(,k);

            if(ch>ll)break;

            ch*=pow(,l);

            if(ch>ll)break;

            ss[p++]=ch;

        }

        sort(ss,ss+p);

    cin>>n;

    int l=;

    int r=p-;

    while(l<r){

        int mid=l+(r-l)/;

        if(ss[mid]>=n){

            r=mid;

        }

        else l=mid+;

    }

    cout<<ss[l]<<endl;

    }

}