/**

题目：poj3208 Apocalypse Someday

链接：http://poj.org/problem?id=3208

题意：求第K(K <= 5*107)个有连续3个6的数。

思路：数位dp+二分。

dp[i][j]表示长度为i，前缀状态为j时含有的个数。

j=0表示含有前导0；

j=1表示前缀连续1个6

j=2表示前缀连续2个6

j=3表示前缀连续3个6

j=4表示前缀不是6；

*/

//#include<bits/stdc++.h>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<map>

#include<algorithm>

#include<queue>

using namespace std;

#define P pair<int,int>

#define ms(x,y) memset(x,y,sizeof x)

#define LL long long

const int maxn = ;

const int mod = 1e9+;

const int maxnode = *+;

const int sigma_size = ;

const LL inf = 1e18;

int digit[];

LL dp[][];///0表示前导0,1表示前缀一个6,2表示前缀2个6,3表示前缀3个6，4表示前缀不是6；

int next_state(int state,int x)

{

    if(state==) return ;

    if(x==){

        if(state==||state==) return state+;

        else return ;

    }else

    {

        return ;

    }

}

LL dfs(int len,int state,int bounded)

{

    if(len==){

        return state==;

    }

    if(!bounded&&dp[len][state]!=-) return dp[len][state];

    int d = bounded?digit[len]:;

    LL ans = ;

    for(int i = ; i <= d; i++){

        if(state==){

            if(i==) ans += dfs(len-,,bounded&&(i==d));

            else ans += dfs(len-,i==?:,bounded&&(i==d));

        }else

        {

            ans += dfs(len-,next_state(state,i),bounded&&(i==d));

        }

    }

    if(!bounded){

        dp[len][state] = ans;

    }

    return ans;

}

LL solve(LL n)

{

    int len = ;

    while(n){

        digit[++len] = n%;

        n /= ;

    }

    return dfs(len,,true);

}

int main()

{

    int T;

    ms(dp,-);

    cin>>T;

    while(T--)

    {

        int n;

        scanf("%d",&n);

        LL lo = , hi = inf, mi;

        while(lo<hi){

            mi = (lo+hi)/;

            LL ans = solve(mi);

            if(ans>=n){///找下界。

                hi = mi;

            }else

            {

                lo = mi+;

            }

        }

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

    }

    return ;

}

/*

*/