众所周知,一场竞赛可以用字符串 $$$s$$$ 来表示,该字符串由表示问题的大写拉丁字母组成。众所周知,如果比赛包含“快速傅里叶变换“或”NTT" 作为连续子字符串。
你的任务是重新排列 $$$s$$$ 竞赛中的问题,使本次竞赛不难。如果最初的比赛不难,你可以保持原样。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^{5}$$$)。
输入数据的附加约束:
- 所有测试用例的字符串总长度不超过 $$$2 \cdot 10^{5}$$$。
输出
对于每个测试用例,输出一个字符串 - 通过重新排列字母从 $$$s$$$ 获得的不难的竞赛。
如果有多个正确答案,则可以输出任何一个。可以证明,至少总是存在一个正确答案。
示例
输入复制
5FFTABFBANTTAFFTNTTFFTFFTFFTNNTNNTAFFTBFFNTTFTTZ
输出复制
FTF ABFBANATT NTFTFT TFFFFFFNTNTNTNT AFTFBTTFFNFTTZ