Для данного слова (последовательности строчных латинских букв) выведите следующее за ним (в лексикографическом порядке) слово, которое может быть получено из данного перестановкой букв (анаграмму). Если данное слово уже является последним среди всех своих анаграмм, то необходимо вывести первую возможную (в лексикографическом порядке) анаграмму.
Входные данные
В первой строке задается число N - количество слов. Далее идет последовательность из N слов, по одному слову в строке. Длина одного слова не превышает 50 символов.
Выходные данные
Необходимо вывести результат для каждого полученного на вход слова.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
aab
aba
baa
aaa |
aba
baa
aab
aaa |