Description

编写一个程序，从已给的字符集合中生成所有可能的字符串。 例如：已知一个字符串“abc”，你编写的程序必须输出：“abc”，“acb”，“bac”，“bca”，“cab”和“cba”。在输入的字符串中，有些字符可能出现多次，你的程序所产生的相同的字符串只能出现一次，并按字典顺序排列。

Input

输入只包含一组数据。第一行包含一个正整数N(1<=N<=10)，表示有N个字符串。接下来N行，每行都有一个字符串。字符串由小写和大写字母组成，应区分大小写。字符串的长度小于10。

Output

对应每组输入字符串，输出应该包含由该字符串生成的所有不同的字符串。由同一个字符串生成的字符串必须按字典顺序排列输出。大写字母在相应的小写字母之前。

Sample

Input

3
aAb
abc
acba

Output

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

Hint

由于大写字母在相应的小写字母之前，所以字符正确的顺序是：'A'<'a'<'B'<'b'<...<'Z'<'z'。

Source: yaojian