#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>v[1000];
char c[200100],f[10],C[100010];
ll ans,a[200100],mx,b[200100],h[1010],e[1010],q[10];
void merge(int l,int mid,int r)
{
    int i,j,k;
    if(l>=r) return;
    merge(l,(mid+l)/2,mid);
    merge(mid+1,(mid+r)/2,r);
    i=l;
    j=mid+1;
    k=l;
    while(i<=mid&&j<=r){

        if(a[i]<=a[j]){

            b[k++]=a[i++];
        }
        else{

            ans=ans+mid-i+1;
            b[k++]=a[j++];
        }
    }
    while(i<=mid){

        b[k++]=a[i++];
    }
    while(j<=r){

        b[k++]=a[j++];
    }
    for(i=l;i<=r;i++) a[i]=b[i];
}
string s;
void solve(){
    ll i,j,cnt=0;
    char ss;
    for(i=1;i<=4;i++){
        ss=f[q[i]];
        v[ss].clear();
        for(j=1;j<=e[ss];j++){
            cnt++;
            v[ss].push_back(cnt);
            c[cnt]=ss;
        }
    }
    h['A']=h['N']=h['T']=h['O']=0;
    for(i=0;i<s.length();i++){
        a[i+1]=v[s[i]][h[s[i]]++];
    }
    ans=0;
    merge(1,(cnt+1)/2,cnt);
    if(mx<ans){
        mx=ans;
        for(i=1;i<=cnt;i++) C[i]=c[i];
    }
}
int main(void){
    ll i,n,t,j,k,z;
    cin>>t;
    f[1]='A',f[2]='N',f[3]='T',f[4]='O';
    while(t--){
        mx=-1;
        cin>>s;
        e['A']=e['N']=e['T']=e['O']=0;
        for(i=0;i<s.length();i++) e[s[i]]++;
        for(i=1;i<=4;i++){
            q[1]=i;
            for(j=1;j<=4;j++){
                if(j==i) continue;
                q[2]=j;
                for(k=1;k<=4;k++){
                    if(k==i||k==j) continue;
                    q[3]=k;
                    for(z=1;z<=4;z++){
                        if(z==i||z==j||z==k) continue;
                        q[4]=z;
                        solve();
                    }
                }
            }
        }
        for(i=1;i<=s.length();i++) printf("%c",C[i]);
        puts("");
    }
}