Generate Palindromic Substrings

Given a string S, a substring is a contiguous sequence of characters in S. A substring is called a palindrome if it reads the same forward and backward. You are required to generate all unique palindromic substrings for each test string and output them in lexicographically sorted order.

The lexicographical order is defined in the usual way over the English alphabet. For example, for the string ababa, the palindromic substrings are: $$\{a, aba, ababa, b, bab\}$$ and when sorted lexicographically, the order remains: a, aba, ababa, b, bab.

Read the input from stdin and output the result to stdout as described in the input and output sections.

inputFormat

The input begins with a single integer T on the first line, representing the number of test cases. Each of the following T lines contains a non-empty string composed only of lowercase English letters.

For example:

3
ababa
abc
aaa

outputFormat

For each test case, print a single line containing the unique palindromic substrings found in the input string, sorted in lexicographical order, with each substring separated by a single space.

For the sample input above, the output should be:

a aba ababa b bab
 a b c
 a aa aaa

## sample

1
ababa

a aba ababa b bab

</p>