时间限制：1秒　　内存限制：256M

---

【问题描述】

　　会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的 八皇后问题。

　　对于某个满足要求的八个皇后的摆放方法，定义一个皇后串 \(a\) 与之对应，即 \(a=x_1x_2...x_8\)，其中 \(x_i\) 为相应摆法中第 \(i\) 行皇后所处的列数。如上图，是一个可行解，我们用序列 15863724 来表示。已经知道八皇后问题一共有92组解（即92个不同的皇后串）。
　　给出一个数 \(n\)，要求输出第 \(n\) 个皇后串。串的比较是这样的：皇后串 \(x\) 在皇后串 \(y\) 之前，当且仅当将 \(x\) 视为整数时比 \(y\) 小，比如：15863724 比 16837425 小。

【输入格式】

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

【输出格式】

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

【输入输出样例】

　Input

2
1
92

　Output

15863724
84136275

【数据说明】

　　对于所有数据，保证 \(1 ≤ t ≤ 50\)，\(1 ≤ n ≤ 92\)。

【来源】

　　Mr.he