Alice decides to challenge Bob to a problem. She gives him a number.

Bob can rearrange the digits of this number by applying pair-wise swaps between any 2 digits in the number as many times as he wants. Now Alice asks him to write down all the distinct numbers that he can form and sort them. Of these she wants him to tell her the 3^rd Smallest and the 3^rd Largest possible number(numerically).

Now the number itself might be quite large having up to 10⁵ digits and it is also known that the number will have only \(1-9\) as digits(Alice does not like 0 for some reason).
Help Bob with this task!

Input:

First line contains T which is the number of test cases.
T lines follow each containing an integer N .

Output:

For each input N, output one line containing the 3^rd Smallest Number and the 3^rd Largest number separated by a space. If it doesn't exist, instead print "Not possible!"(without the quotes)

Constraints:

• \(1 \le T \le 10\)
• \(1 \le No \, of \, digits \, in \, N \le 10^5\)

Scoring:

• \(1 \le T \le 10, 1 \le No \, of \, digits \, in \, N \le 10 \) (20 pts)
• \(1 \le T \le 10, 10 \le No \, of \, digits \, in \, N \le 10^3\) (30 pts)
• \(1 \le T \le 10, 1000 \le No \, of \, digits \, in \, N \le 10^5\) (50 pts)