Вам слід написати програму, яка згенерує усі можливі слова із заданого набору літер.

Наприклад, зі слова "abc" в результаті перестановки літер можна отримати слова "abc", "acb", "bac", "bca", "cab" та "cba".

Вхідні слова можуть містити декілька однакових літер. Ваша програма не повинна виводити одне і те ж слово більше одного разу. Усі слова слід виводити по зростанню в алфавітному порядку.

Вхідні дані

Перший рядок містить кількість тестів. Кожний наступний рядок містить слово з літер латинського алфавіту (від A до Z). Літери верхнього та нижнього регістру вважати різними.

Вихідні дані

Для кожного тесту вивести усі можливі слова, які можна отримати із заданих літер, у зростаючому алфавітному порядку. Кожне слово виводити в окремому рядку. В алфавітному порядку літера верхнього регістру менша за відповідну літеру нижнього регістру.