Dani and Mike are two kids ,They are playing games all day and when they don't find a game to play they invent a game . There is about an hour to arrive to school, because they love playing with strings Dani invented a game , Given a string and the winner is the first who form a palindrome string using all letters of this string according to the following sample rules : 1- player can rearrange letters to form a string . 2- the formed string must be palindrome and use all letters of the given string. 3- if there is more than one string chose the lexicographically smallest string . EX: string is "abacb" player can form : "abcba" and "bacab" ,but "abcba" is the lexicographically smallest. Mike asked you to write a Program to compute the palindrome string so he can beat Dani.
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 1000). Every test case on one line contain one string ,the length of the string will not exceed 1000 lower case English letter.
For each test case print a single line containing the lexicographically smallest palindrome string according to the rules above. If there is no such string print "impossible"
4
abacb
acmicpc
aabaab
bsbttxs
abcba
impossible
aabbaa
bstxtsb
Palindrome string is a string which reads the same backward or forward.
Lexicographic order means that the strings are arranged in the way as they appear in a dictionary.
Name |
---|