（参考蓝书）。

首先依照 P7690 [CEOI2002] A decorative fence 的思路，我们通过试填法来确定这个数。为了快速得到方案数，我们考虑 DP。

设 $f_{i,j}$ 为当前数有 $i$ 位，$j=0$ 表示最后一位不是 $6$，$j=1$ 表示最后一位是 $6$，但前一位不是，$j=2$ 表示我们从当前位连通的 $6$ 有两个，$j=3$ 表示我们已经凑出了一个魔鬼数。$f_{i,j}$ 记录这些情况的方案数（可含前导零，方便计算）。

决策当前位上的数字，得到以下状态转移方程：

$$ \begin{aligned} f_{i,0}&=(f_{i-1,0}+f_{i-1,1}+f_{i-1,2}) \times 9\\ f_{i,j(1\le j \le 2)}&=f_{i-1,j-1}\\ f_{i,3}&=f_{i-1,3} \times 10+f_{i-1,2} \end{aligned} $$

接下来，按照刚刚的描述，我们来讨论试填法的具体过程。

先确定位数 $len$。

对于每一位 $i$（从高位到低位，方便输出），枚举当前位的数 $p$：

1. $cnt$ 表示我们如果把这一位赋值为 $p$ 的魔鬼数方案数，首先先赋值 $cnt$ 为当前数后有魔鬼数后继的方案数 $f_{i-1,3}$。

2. 如果当前数为 $6$ 的后继，或者我们已经有了一个魔鬼数后缀，那么我们还要把 $cnt$ 加上可以接上当前前缀的方案数。

3. 如果 $cnt<n$，将 $n$ 减去 $cnt$，然后继续枚举当前位的取值。否则说明这一位就是 $p$，输出 $p$，然后更新连续 $6$ 的个数，跳转至下一位。

这样，我们就用试填法填出了这个数。

至此，我们解决了这个问题，这是试填法思想带给我们的力量。

// Problem: P10958 启示录
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10958
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

//try fill
#include <bits/stdc++.h>
#define int __int128
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
signed n;
int f[30][4];
void prework() {
    f[0][0] = 1;
    upp(i, 1, 20) {
        f[i][0] = 9 * (f[i - 1][0] + f[i - 1][1] + f[i - 1][2]);
        f[i][1] = f[i - 1][0];
        f[i][2] = f[i - 1][1];
        f[i][3] = f[i - 1][3] * 10 + f[i - 1][2];
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    signed tt;
    cin >> tt;
    prework();
    while (tt--) {
        cin >> n;
        int len = 3;
        while (f[len][3] < n) len++; // sure about the len
        // next try to fill the number
        int now = 0;
        dww(i, len, 1) { // reverse to solve
            upp(j, 0, 9) {
                int cnt = f[i - 1][3];
                if (now == 3 || j == 6) { // to know the in-law works
                    upp(k, max((int)0, 3 - now - (j == 6)), 2) cnt += f[i - 1][k];
                }
                if (cnt < n)
                    n -= cnt;
                else {
                    if (now < 3) {
                        if (j == 6)
                            now++;
                        else
                            now = 0;
                    }
                    cout << ((signed)j);
                    break;
                }
            }
        }
        cout << endl;
    }
    return 0;
}