Constructing the Lexicographically Smallest Palindrome

You are given a string s and you are required to rearrange its characters to form a palindrome. If it is possible to form a palindrome, output the lexicographically smallest palindrome that can be constructed using all characters of the string; otherwise, output "Impossible".

A palindrome is a string that reads the same forward and backward. The lexicographically smallest palindrome is the one that would appear first in a dictionary amongst all possible palindromic permutations. The solution should read input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The first line contains an integer T, indicating the number of test cases. Then T lines follow, each containing a single string s. Input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the lexicographically smallest palindrome that can be formed from the characters of s, or "Impossible" if no such palindrome exists. The output should be printed to standard output (stdout).## sample

2
civic
aabbcc

civic
abccba