2021.11.09/dfs/八皇后
https://www.acwing.com/problem/content/description/3475/
贴个简单题吧，代码就注释了，毕竟凌晨3.50了

#include <bits/stdc++.h>
using namespace std;

int n, used, st[10], tmp;
bool wz[11][11], duijiaoxian[20], xieduijiaoxian[40];
vector<int> v;

void dfs(int u){
    if(u == 8){
        v.push_back(tmp);

        return ;
    }

    for(int i = 1; i <= 8; i++){
        if(((used >> i) & 1) == 0 && duijiaoxian[i + u] == 0 && xieduijiaoxian[u - i + 20] == 0){
            //一定要用((used >> i) & 1) == 0
            //不能用：(used >> i) & 1 == 0
            xieduijiaoxian[u - i + 20] = 1;
            duijiaoxian[i + u] = 1;
            used += (1 << i);
            wz[u][i] = 1; //st[u] = i;
            tmp *= 10, tmp += i;

            dfs(u + 1);

            tmp /= 10;
            duijiaoxian[i + u] = 0;
            xieduijiaoxian[u - i + 20] = 0;
            used -= (1 << i);
            wz[u][i] = 0;   //st[u] = 0;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    dfs(0);
    sort(v.begin(), v.end());

    int tt;cin >> tt;
    while(tt--){
        cin >> n; cout << v[n - 1] << endl;
    }
    return 0;
}