皇后問題的解法

會下國際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數地吃掉其他棋子。如何將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的皇后串

輸入樣例