描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

输出

输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

样例输入

2
1
92

样例输出

15863724
84136275

# endcoding : UTF-8
"""
@author = 寻找任大侠
@email = renjx@stu.pku.edu.cn
@create_time = 2021/11/13 17:18
"""
n = 8
col_flag = [0 for i in range(n)] #列标
iter_up = [0 for i in range(2 * n - 1)]#上斜对角 iter_up[row+col] = 1
iter_low = [0 for i in range(2 * n - 1)]  # 下斜对角 iter_up[row-col+n-1] = 1
q_list = []
q_str = [0 for i in range(n)]

def search_eight_queen(row):
    for col in range(n):
        if col_flag[col] == 0 and iter_up[row + col] == 0 \
                and iter_low[row - col + n - 1] == 0:
            q_str[row] += col + 1
            col_flag[col] = iter_up[row + col] = iter_low[row - col + n - 1] = 1
            if row < n - 1:
                search_eight_queen(row + 1)
            else:
                q_list.append(''.join(map(str, q_str)))
            col_flag[col] = iter_up[row + col] = iter_low[row - col + n - 1] =\
                q_str[row] = 0

search_eight_queen(0)
# 天然有序，递归的过程符合行从小到大
# q_list = sorted(q_list) 
num = int(input())
for i in range(num):
    i = int(input())
    print(q_list[i - 1])