Fishhead's problem for post 90s

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

thinking610 is proud because of born after 1990.He loves the number "90".When fishhead asked him to give a problem,he came up soon.
There is a string containing only decimal digit characters. The length of the string is between 1 and 1000. Using characters of the string, you have to construct the maximum number which divides by 90 without remainder. Each character of the string may not be used more than once.

Input

The first line of the input contains an integer T (T <= 1000), indicating the number of cases. Each case begins with a line containing a single line representing the source string.

Output

For each test case, print a line containing the decimal representation of the maximum number (leading zeroes should be omitted). If no number can be constructed, please output “impossible” instead.

Sample Input

3
0099
2
00

Sample Output

9900
impossible
0

Hint

None

Source

水果杯之窦煜峰专场练习赛

提交代码