//100gods

#include <bits/stdc++.h>
#define int long long
#define vec2 vector<vector<int>>
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define FRE freopen("elegant.in","r",stdin);freopen("elegant.out","w",stdout)
#define pii pair <int,int>
#define vii vector <int>
#define vpii vector <pii>
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define minii LLONG_MAX
#define all(x) x.begin(), x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define double long double
#define eb emplace_back
const double pi = 3.1415926535898;
const int mod=1e9+7;
//const int mod=998244353;

using namespace std;

int tree[400001],n;
string s;
map <char,int>m;
map <int,char>rm;
int vis[4];
vii v;
string ans;
int maxi;


void build(int l,int r,int k)
{
    if (l==r)
    {
        tree[k]=0;
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,2*k+1);
    build(mid+1,r,2*k+2);
    tree[k]=tree[2*k+1]+tree[2*k+2];
}

int findd(int l,int r,int k,int x,int y)
{
    if (y<l||x>r)
    {
        return 0;
    }
    if (x<=l&&r<=y)
    {
        return tree[k];
    }
    int mid=(l+r)/2;
    return (findd(l,mid,2*k+1,x,y)+findd(mid+1,r,2*k+2,x,y));
}

void update(int l,int r,int k,int x,int w)
{
    if (x>r||x<l)
    {
        return;
    }
    if (l==r&&x==l)
    {
        tree[k]+=w;
        return ;
    }
    int mid=(l+r)/2;
    update(l,mid,2*k+1,x,w);
    update(mid+1,r,2*k+2,x,w);
    tree[k]=tree[2*k+1]+tree[2*k+2];
}

void findval()
{
    int sum=0;
    int prev=0;
    string t;
    for (int j=0;j<4;j++)
    {
        for (int i=0;i<n;i++)
        {
            if (m[s[i]]==v[j])
            {
                int val=prev+findd(0,n-1,0,0,i);
                sum+=val;
                prev++;
                update(0,n-1,0,i,-1);
                t+=rm[v[j]];
            }
        }
    }
    //cout<<sum<<"\n";
    if (maxi<sum)
    {
        maxi=sum;
        ans=t;
    }
    //cout<<ans<<"\n";
}

void brute(int pos)
{
    if (pos==4)
    {
        build(0,n-1,0);
        findval();
        return ;
    }
    for (int i=0;i<4;i++)
    {
        if (!vis[i])
        {
            vis[i]=1;
            v.pb(i);
            brute(pos+1);
            v.pop_back();
            vis[i]=0;
        }
    }
}


int32_t main()
{
    fio;
    int t;
    cin>>t;
    while (t--)
    {
        maxi=-1;
        ans.clear();
        cin>>s;
        n=s.length();
        m['A']=0;
        m['N']=1;
        m['O']=2;
        m['T']=3;
        rm[0]='A';
        rm[1]='N';
        rm[2]='O';
        rm[3]='T';
        brute(0);
        cout<<ans<<"\n";
    }
    return 0;
}
