Description

写程序从一组给定的字母中生成所有可能的单词。例如，给定单词$“abc”$，应该输出单词$“abc”“acb”“bac”“bca”“cab”$和$“cba”$。在输入的单词中，某些字母可能会出现多次。对于给定的单词，程序不应多次生成同一个单词，并且这些单词应按字母升序输出。

Format

Input

输入由几个单词组成。第$1$行包含一个数字，表示单词数。以下每行各包含一个单词。单词由$a$到$z$的大小写字母组成。大小写字母应被视为不同。每个单词的长度都小于$13$。

Output

对于输入中的每个单词，输出应该包含所有可以用给定单词的字母生成的不同单词。由同一输入词生成的词应按字母升序输出。大写字母在对应的小写字母之前。

提示： 大写字母在相应的小写字母之前，所以正确的字母顺序是：$'A'<'a'<'B'<'b'<…<'Z'<'z'。$

Samples

3
aAb
abc
acba

Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

来源

POJ1256