#232. 八皇后

八皇后

【题目描述】

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

对于某个满足要求的8皇后的摆放方法,定义一个皇后串a与之对应,即a=b1b2...b8a=b_1b_2...b_8,其中bib_i为相应摆法中第ii行皇后所处的列数。已经知道88皇后问题一共有9292组解(即9292个不同的皇后串)。

给出一个数bb,要求输出第bb个串。串的比较是这样的:皇后串xx置于皇后串yy之前,当且仅当将xx视为整数时比yy小。

【输入】

11行是测试数据的组数nn,后面跟着nn行输入。每组测试数据占11行,包括一个正整数b(1b92)b(1≤b≤92)

【输出】

输出有nn行,每行输出对应一个输入。输出应是一个正整数,是对应于bb的皇后串。

【输入样例】

2
1
92

【输出样例】

15863724
84136275