题目描述

在国际象棋中，皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。八皇后问题要求将 $8$ 个皇后放在 $8 \times 8$ 的棋盘上，使得它们互不攻击。

对于每个满足要求的摆放方法，定义一个皇后串 $a = b_1b_2\ldots b_8$，其中 $b_i$ 表示第 $i$ 行皇后所在的列数（从 $1$ 开始编号）。已知八皇后问题共有 $92$ 组解（即 $92$ 个不同的皇后串）。

给出一个数 $b$，要求输出第 $b$ 个皇后串。串的比较规则是：将皇后串视为整数，按整数大小排序。

输入格式

第一行一个整数 $n$，表示测试数据的组数。

接下来 $n$ 行，每行一个正整数 $b$，表示要查询的皇后串序号。

输出格式

输出 $n$ 行，每行一个正整数，表示对应输入的皇后串。

2
1
92

15863724
84136275

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 100$，$1 \leq b \leq 92$。