## Problem: Pallindrome Patterns

Given a string S, find out all the possible palindromes that can be generated using the letters of the string and print them in lexicographical order.

Input
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains the string S.

Output
Print out all the combinations in lexicographical order, seprated by a space inside curly brackets, i.e { palindrome1 palindrome 2}. If no pallindromes can be formed, print empty braces { }.

Constraints
1 <= T <= 100
0 < S <= 20

Examples

Input
3
abbab
abcabc
abc

Output
{ abbba babab }
{ abccba acbbca baccab bcaacb cabbac cbaabc }
{ }

Using itertools in python
Python 2.7

from itertools import *
def pallindrome_permute(s):
"""
return permutations of s that is a
pallindrome string
"""
res = set(list(permutations(s)))
for x in res:
x = ''.join(x)
if is_pallindrome(x):
yield x

def is_pallindrome(s):
"""
check if a string is pallindrome
"""
length = len(s)
length_2 = length/2
for _ in range(length_2):
if s[_] != s[length-1-_]:
return False
else:
return True

if __name__ == '__main__':
t = input()
for _ in range(t):
s = raw_input().strip()
print "{",
for _ in sorted(list(pallindrome_permute(s))):
print _,
print "}"