Distinct Palindromic Subsequences

You are given a string s. Your task is to generate all distinct non-empty subsequences of s that are palindromes, and output them in lexicographical order.

A subsequence is a sequence that can be derived from the original string by deleting zero or more characters without changing the order of the remaining characters. A palindrome is a sequence that reads the same backwards as forwards.

If no palindromic subsequence is found (for example, when s is an empty string), output a single token None.

You will be given multiple test cases. For each test case, process the string as described above and print the result on a new line with each palindromic subsequence separated by a single space.

Note: The constraints are such that the length of the string is small enough to allow a brute force generation of all subsequences.

inputFormat

The input begins with an integer t representing the number of test cases. Each of the following t lines contains a string s.

Input Format:

 t
 s1
 s2
 ...
 st

outputFormat

For each test case, output a single line containing the distinct palindromic subsequences of the given string in lexicographical order, separated by a single space. If there is no palindromic subsequence (i.e. the string is empty), output None.

## sample

2
aab
abc

a aa b
a b c

</p>