URI Online Judge | 1919

Help Nhonho

By Dâmi Henrique, Inatel BR Brazil

Timelimit: 1

After Teacher Girafales find out that Nhonho was missing classes and asking Chaves to sign his name on the attendance list in exchange for a bread with ham, Nhonho began to receive every week a special challenge from Girafales, and if Nhonho did not solve them, Girafales would tell Nhonho fathers about the attendance list fact.

The challenge of the week is called "Permuted Sum" and he needs to solve the following puzzle: abc + acb + bac + bca + cab + cba = K, given a value of K, with no digit repeats occur (a ≠ b ≠ c).

If we have K = 1332, one of the possible solutions is to use a = 1, b = 2 and c = 3, if we sum their permutations: 123 + 132 + 213 + 231 + 312 + 321 = 1332.

Another solution is: a = 0, b = 1, c = 5: 015 + 051 + 105 + 150 + 501 + 510 = 1332.

The above explanations used only 3 digits to easily understanding, the real problem, which Teacher Girafales asked Nhonho and you have to help him to solve, consists of 5 digits, and you have to consider all its permutations (abcde + abced + ..... + edcba), with no digit repetition (a ≠ b ≠ c ≠ d ≠ e).

Given the value of K, output, lexicographically, all possible sets of numbers that satisfy the Girafales puzzle.

Input

The first line of input has an integer T, indicating the number of test cases. Each of the following lines T contains an integer K (1 ≤ K ≤ 107), as described above.

Output

For each case, output lexicographically all the sets of values {a, b, c, d, e} that solve the Girafales puzzle or "impossivel" if there is no solution.

Leave a blank line after each test case. Check the output formatting.

Input Sample Output Sample

3

9066576

8731231

3199968

{4,6,7,8,9}

impossivel

{0,1,2,3,6}

{0,1,2,4,5}