题目描述

一场比赛可以用表示其题目的一些大写英文字母构成的字符串 $s$ 表示。当其中含有“FFT”或“NTT”作为它的连续子串时，我们称这场比赛是困难的。

你的任务是重排 $s$ 的题目使得这场比赛不再困难。如果初始时这场比赛就不困难，你可以让它保持原样。

输入格式

多组数据。第一行一个整数 $t(1\le t\le 10^4)$，表示数据组数。

对于每组数据，输入一行一个字符串 $s(1\le\vert s\vert\le 2\times 10^5)$。

保证单个测试点中字符串长度的和不超过 $2\times 10^5$。

输出格式

对于每组数据，输出一行一个字符串，为重排 $s$ 的字符得到的一场不困难的比赛。

如果有多种解，输出任意一种均可。可以证明总是存在至少一种解。

样例

5
FFT
ABFBANTTA
FFTNTT
FFTFFTFFTNNTNNT
AFFTBFFNTTFTTZ

FTF
ABFBANATT
NTFTFT
TFFFFFFNTNTNTNT
AFTFBTTFFNFTTZ