Anagram

Time limit1sMemory limit128 MB

Summary

For each given word, print every distinct string formed by rearranging its letters, in lexicographic order with duplicates removed.

Level: Medium6 of 10
Topics: Backtracking, Sorting, Recursion, Combinatorics
Solved: No attempts yet

Problem

An anagram program prints every distinct word that can be formed by rearranging the letters of a given word. For example, given abc, it prints abc, acb, bac, bca, cab, cba.

A word may contain repeated letters, so the same string can be formed more than once; print each distinct string only once. For each word, print its anagrams in alphabetical (lexicographic) order.

Input

The first line contains the number of words $N$ . Each of the next $N$ lines contains one word made only of lowercase English letters. Every word has length at most 20, and only words whose number of distinct anagrams is at most 100,000 are given.

Output

For each word, print all of its anagrams, one per line, in lexicographic order with duplicates removed.

Examples3

Example 1

Input

2
abc
acba

Expected output

abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

Example 2
Input
```
1
a
```
Expected output
```
a
```
Example 3
Input
```
1
aab
```
Expected output
```
aab
aba
baa
```