在拒绝$$$10^{100}$$$数据结构问题后,Errorgorn对Anton非常生气并决定杀了他。
Anton 的 DNA 可以表示为字符串 $$$a$$$,其中仅包含字符“ANTON”(只有 $$$4$$$ 不同字符)。
Errorgorn 可以将 Anton 的 DNA 更改为字符串 $$$b$$$,该字符串必须是 $$$a$$$ 的排列。不过,安东的身体却可以抵御这种攻击。在$$$1$$$秒内,他的身体可以交换他DNA中的$$$2$$$相邻字符,将其变回$$$a$$$。安东的身体很聪明,会用最少的动作。
为了最大限度地提高安东死亡的机会,Errorgorn 想要改变安东的 DNA,使安东的身体恢复 DNA 的时间最大化。但由于 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$$$ 的排列。
示例
输入 #1
4 ANTON NAAN AAAAAA OAANTTON
输出 #1
NNOTA AANN AAAAAA TNNTAOOA
注意
对于第一个测试用例,Anton 的身体需要 $$$7$$$ 秒才能将 NNOTA 转换为 ANTON:
NNOTA $$$\to$$$ NNOAT $$$\to$$$ NNAOT $$$\to$$$ NANOT $$$\to$$$ NANTO $$$\to$$$ ANNTO $$$\to$$$ ANTNO $$$\to$$$ 安东。
请注意,您无法输出 AANTON、ANTONTRYGUB、AAAAA 和 anton 等字符串,因为它不是 ANTON 的排列。
对于第二个测试用例,Anton 的身体需要 $$$2$$$ 秒将 AANN 转换为 NAAN。请注意,其他字符串(例如 NNAA 和 ANNA)也将被接受。