Fishhead's problem for post 90s
Time Limit: 1000 ms
Memory Limit: 65535 ms
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.
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.
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.