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 3rd Smallest and the 3rd Largest possible number(numerically).
Now the number itself might be quite large having up to 105 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!
First line contains T which is the number of test cases.
T lines follow each containing an integer N .
For each input N, output one line containing the 3rd Smallest Number and the 3rd Largest number separated by a space. If it doesn't exist, instead print "Not possible!"(without the quotes)
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.