← 返回题目列表

Codeforces · 2125/A

A. 艰难的比赛

中文机器翻译题面 查看原题

众所周知,一场竞赛可以用字符串 $$$s$$$ 来表示,该字符串由表示问题的大写拉丁字母组成。众所周知,如果比赛包含“快速傅里叶变换“或”NTT" 作为连续子字符串。

你的任务是重新排列 $$$s$$$ 竞赛中的问题,使本次竞赛不难。如果最初的比赛不难,你可以保持原样。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^{5}$$$)。

输入数据的附加约束:

  • 所有测试用例的字符串总长度不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,输出一个字符串 - 通过重新排列字母从 $$$s$$$ 获得的不难的竞赛。

如果有多个正确答案,则可以输出任何一个。可以证明,至少总是存在一个正确答案。

示例

输入
复制

5
FFT
ABFBANTTA
FFTNTT
FFTFFTFFTNNTNNT
AFFTBFFNTTFTTZ

输出
复制

FTF
ABFBANATT
NTFTFT
TFFFFFFNTNTNTNT
AFTFBTTFFNFTTZ