#pragma optimization_level 3
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
    
using namespace std;
    
#define  fastio         ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
#define  randomINIT     mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep for(ll i=0;i<n;i++)
#define fori(a,b,c) for(ll i=a;i<=b;i=i+c)
#define pr(val) cout<<val<<endl
    
int main(){
    ll t;
    cin>>t;
    while(t--){
        ll n;
        string a;
        cin>>a;
        n = a.length();
        vector<char> ch(3,'w');

        
        if(a[0] == a[n-1]) pr("NO");
        else{
            ch[a[0]-'A'] = '(';
            ch[a[n-1]-'A'] = ')';

            int ind=0;
            for(auto &e:ch){
                if(e=='w'){
                    e = '(';
                    break;
                }
                ind++;
            }
            ll check=0,f=0,ok=0;

            for(auto e:a){
                if(ch[e-'A']=='(') check++;
                else check--;

                if(check<0) f++;
            }
            if(check!=0 || f!=0){
                //pr("gg");
                f++;
            }
            else ok = 1;
            ch[ind] = ')';


            check=0,f=0;
            for(auto e:a){
                if(ch[e-'A']=='(') check++;
                else check--;

                if(check<0) f++;
            }
            if(check!=0 || f!=0) f++;
            else ok = 1;


            if(ok) pr("YES");
            else pr("NO"); 
        }
    }
}