The Eight Queens

Problem Background

Special for beginners, ^_^

Problem Description

Anyone who plays chess knows: a queen can capture any other piece along rows, columns, and diagonals without step limit. How to place 8 queens on the board (an $8 \times 8$ grid) so that none of them can be captured! This is the famous Eight Queens problem.

For a valid placement of the 8 queens, define a queen string $a$ corresponding to it: $a = b_1b_2\dots b_8$, where $b_i$ is the column number of the queen in the $i$-th row. It is known that the Eight Queens problem has $92$ solutions in total (i.e., $92$ distinct queen strings).

Given a number $b$, output the $b$-th string. The strings are compared as follows: queen string $x$ precedes queen string $y$ if and only if, when $x$ and $y$ are viewed as integers, $x$ is smaller than $y$.

Input Format

The first line is the number of test cases $n$, followed by $n$ lines of input. Each test case occupies one line and contains a positive integer $b\;(1 \le b \le 92)$.

Output Format

Output $n$ lines, each line outputting the result corresponding to one input. The output should be a positive integer, the queen string corresponding to $b$.

Sample Input

2
1
92

Sample Output

15863724
84136275

Constraints

Time limit: 1s, memory limit: 1024KiB for each test case.