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^5 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 ≤ T ≤ 10
1 ≤ No \, of \, digits \, in \, N ≤ 10^5

Scoring:

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

SAMPLE INPUT
3
123
4
1232

SAMPLE OUTPUT
213 231
Not possible!
1322 3122

Explanation

Case 1: We can make these numbers from 123 {123,132,213,231,312,321}. Of these the 3rd from the front is 213 and from back is 231.

Case 2: We can only make 4 from this. Hence it is not possible!

Case 3: We can make 12 distinct numbers from this number. The smallest 3 are 1223, 1232, 1322. The largest 3 are 3221,3212,3122.

见题面

见题面