Problem 2 : Permutations

Problem

Given a word, write a program to generate all its permutations in lexicographic order.

Input

The input will consist of several words. The first line contains the number of words. It is followed by that many words, each appearing in single line. The words will have both uppercase and lowercase letters in them, and they are to be considered different.

Output

For each given word in the input, print its all possible permutations, each on a different line. The different permutations should be printed in lexicographic order. An uppercase letter goes before the corresponding lowercase letter.

Sample Input

2
aAb
acba

Sample Output

Aab
Aba
aAb
abA
bAa
baA
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa