Description

Chess players are well aware that a queen can capture any other piece in an unlimited number of steps along the same row, column, or diagonal. The problem of placing eight queens on an 8×8 chessboard such that no two queens threaten each other is famously known as the Eight Queens Puzzle.

For any valid arrangement of the eight queens, a corresponding queen string a can be defined as $a = b\_1b\_2...b\_8$, where $b_i$ represents the column number of the queen in the i-th row. It is known that there are a total of 92 distinct solutions (i.e., 92 unique queen strings) to the Eight Queens Puzzle.

Given a number b, your task is to output the b-th queen string. The comparison between queen strings is based on their integer values: string x is considered to come before string y if and only if the integer representation of x is smaller than that of y.

Input Format

The first line contains the number of test cases n, followed by n lines of input. Each test case consists of a single line with a positive integer b (1 ≤ b ≤ 92).

Output Format

Output n lines, each corresponding to an input. Each line should contain a positive integer representing the queen string associated with the given b.

2
1
92

15863724
84136275