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

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

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

Входные данные

Первая строка содержит количество тестов. Каждая следующая строка содержит слово из букв латинского алфавита (от A до Z). Буквы верхнего и нижнего регистра считать различными.

Выходные данные

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