/**
题目：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 = 1005;
const int mod = 1e9+7;
const int maxnode = 100000*6+10;
const int sigma_size = 26;
const LL inf = 1e18;
int digit[22];
LL dp[22][5];///0表示前导0,1表示前缀一个6,2表示前缀2个6,3表示前缀3个6，4表示前缀不是6；
int next_state(int state,int x)
{
if(state==3) return 3;
if(x==6){
if(state==1||state==2) return state+1;
else return 1;
}else
{
return 4;
}
}
LL dfs(int len,int state,int bounded)
{
if(len==0){
return state==3;
}
if(!bounded&&dp[len][state]!=-1) return dp[len][state];
int d = bounded?digit[len]:9;
LL ans = 0;
for(int i = 0; i <= d; i++){
if(state==0){
if(i==0) ans += dfs(len-1,0,bounded&&(i==d));
else ans += dfs(len-1,i==6?1:4,bounded&&(i==d));
}else
{
ans += dfs(len-1,next_state(state,i),bounded&&(i==d));
}
}
if(!bounded){
dp[len][state] = ans;
}
return ans;
}
LL solve(LL n)
{
int len = 0;
while(n){
digit[++len] = n%10;
n /= 10;
}
return dfs(len,0,true);
}
int main()
{
int T;
ms(dp,-1);
cin>>T;
while(T--)
{
int n;
scanf("%d",&n);
LL lo = 1, hi = inf, mi;
while(lo<hi){
mi = (lo+hi)/2;
LL ans = solve(mi);
if(ans>=n){///找下界。
hi = mi;
}else
{
lo = mi+1;
}
}
printf("%lld
",hi);
}
return 0;
}
/*
*/
