D. Убить Антона
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После того, как Антон отклонил $$$10^{100}$$$ задач на структуры данных, Errorgorn очень зол на него и решил его убить.

ДНК Антона можно представить в виде строки $$$a$$$, которая содержит только символы из строки «ANTON» (всего $$$4$$$ различных символов).

Errorgorn может заменить ДНК Антона на строку $$$b$$$, которая должна быть перестановкой $$$a$$$. Однако тело Антона может защититься от этой атаки. За $$$1$$$ секунду его тело может поменять местами $$$2$$$ соседних символа его ДНК, чтобы превратить ее обратно в $$$a$$$. Тело Антона умно и будет использовать минимальное количество ходов.

Чтобы максимизировать вероятность смерти Антона, Errorgorn хочет изменить ДНК Антона на строку, которая максимизирует время, необходимое телу Антона для возвращения к его исходному ДНК. Но поскольку Errorgorn занят решением новых задач на структуры данных, ему нужна ваша помощь, чтобы найти лучшую строку $$$B$$$. Сможете ли вы ему помочь?

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

Первая строка ввода содержит одно целое число $$$t$$$ $$$(1 \leq t \leq 100000)$$$ — количество наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит $$$1$$$ строку $$$a$$$ ($$$1 \leq |a| \leq 100000$$$). $$$a$$$ состоит только из символов "A", "N", "O" и "T".

Гарантируется, что сумма $$$|a|$$$ по всем тестовым примерам не превышает $$$100000$$$.

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

Для каждого набора входных данных выведите единственную строку $$$b$$$. Если ответов несколько, вы можете вывести любой из них. $$$b$$$ должна быть перестановкой строки $$$a$$$.

Пример
Входные данные
4
ANTON
NAAN
AAAAAA
OAANTTON
Выходные данные
NNOTA
AANN
AAAAAA
TNNTAOOA
Примечание

Для первого набора входных данных, телу Антона требуется $$$7$$$ секунд, чтобы превратить NNOTA в ANTON:

NNOTA $$$\to$$$ NNOAT $$$\to$$$ NNAOT $$$\to$$$ NANOT $$$\to$$$ NANTO $$$\to$$$ ANNTO $$$\to$$$ ANTNO $$$\to$$$ ANTON.

Обратите внимание, что нельзя вывести такие строки, как AANTON, ANTONTRYGUB, AAA и anton, так как они не являются перестановкой ANTON.

Для первого тестового случая телу Антона требуется $$$2$$$ секунды, чтобы преобразовать AANN в NAAN. Обратите внимание, что другие строки, такие как NNAA и ANNA также будут приняты.