思路：
这题和南京站的Evil Coordinate有着异曲同工之妙。南京的那题的解法也是一定存在某个最优情况中，相同类型的字母连续出现，然后只需要枚举种情况就可以找到最优解。南京那题我不会证，但是多画几个图后发现找不到反例，感觉也有点道理，这题看了一下证明没看懂，感觉是就是吧。

枚举出来一个状态后计算恢复它最小需要多少步可以用到前缀和，，每个前面的数量分别为，那么需要的最小的步数就是；每个前面的数量分别为，那么需要的最小的步数就是

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7, mod = 1e9 + 7;
string s,tmp="ANTO";
int mp[26],n;
ll f[4][4],cnt[4];
inline void solve() {
    cin>>s;
    n=s.size();
    memset(f,0,sizeof f);
    memset(cnt,0,sizeof cnt);
    for(char i:s) cnt[mp[i-'A']]+=1;
    for(int i=0; i<4; ++i) {
        ll sum(0);
        for(int j=0; j<n; ++j) {
            f[i][mp[s[j]-'A']]+=sum;
            if(s[j]==tmp[i]) sum+=1;
        }
    }
    ll mx=-1;
    vector<int>ans,v= {0,1,2,3};
    do {
        ll num(0);
        for(int i=0; i<4; ++i)
            for(int j=i+1; j<4; ++j) num+=f[v[j]][v[i]];
        if(num>mx) {
            mx=num;
            ans=v;
        }
    } while(next_permutation(v.begin(),v.end()));
    for(int &i:ans) for(int j=0; j<cnt[i]; ++j) cout<<tmp[i];
    cout<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;
    mp[0]=0,mp['N'-'A']=1,mp['T'-'A']=2,mp['O'-'A']=3;
    cin>>_;
    while(_--) solve();
    return 0;
}