数位DP，见注释

参考文献

算法竞赛进阶指南

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;
const int N=30,M=4;
#define int long long 
typedef long long LL;
LL f[N][M];
signed main(){
    //预处理 f[i][j],j≤2：长度是i, 开头已经有j<=2个非魔鬼数的个数
    //       f[i][3] 长度是i的魔鬼数个数
    f[0][0]=1;
    for(int i=1;i<N;++i){
        for(int j=0;j<=3;++j){
            if(j) f[i][j]+=f[i-1][j-1];
            if(j<3) f[i][0]+=f[i-1][j]*9;
        }
        f[i][3]+=f[i-1][3]*10;
    }
    int T;
    scanf("%lld",&T);
    while(T--){
        int n,m;
        scanf("%lld",&n);
        //第n个魔鬼数有m位
        for(m=3;f[m][3]<n;++m);
        //枚举魔鬼数第i位的数字，k表示i位前有6的个数
        for(int i=m,k=0;i;--i){
            for(int j=0;j<=9;++j){
                //长度是i-1的恶魔数
                LL cnt=f[i-1][3];
                //长度是i-1的数和前k个6可以凑出来的恶魔数
                if(j==6||k==3){
                    for(int l=max(3-k-(j==6),0ll);l<3;++l){
                        cnt+=f[i-1][l];
                    }
                }
                if(cnt<n) n-=cnt;
                else {
                    if(k<3) {
                        if(j==6) k++;
                        else k=0;
                    }
                    cout<<j;
                    break;
                }
            }
        }
        cout<<endl;
    }
    return 0;
}