Smallest Lexicographical Palindrome

You are given a string and your task is to determine if it is possible to rearrange its characters to form a palindrome. If it is possible, you should construct the palindrome such that it is the smallest in lexicographical order. Otherwise, output NOT POSSIBLE.

A palindrome is a string that reads the same backwards and forwards. A necessary and sufficient condition for the characters of a string s to be rearranged into a palindrome is that at most one character occurs an odd number of times, i.e., \( oddCount \le 1 \).

Example:

• For the input string aabb, one possible palindrome is abba, which is the smallest lexicographical palindrome.
• For the input string abc, it is not possible to form any palindrome.

The input will be provided from stdin and the output should be printed to stdout.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the following T lines contains a non-empty string.

Example:

2
aabb
abc

outputFormat

For each test case, print the smallest lexicographical palindrome that can be formed using the characters of the input string. If it is not possible to form any palindrome, print NOT POSSIBLE.

Each result should be printed on a new line.

## sample

1
aabb

abba

</p>