#include <bits/stdc++.h> 
using namespace std;
typedef long long int ll;

void solve(){
        
    string s;
    cin>>s;

    int a, b, c, count = 0;
    a = b = c = 0;
    char max; bool check = true;

    for(int i = 0; i < s.length(); i++){
        if(s[i] == 'A') a++;
        else if(s[i] == 'B') b++;
        else c++;
    }

    if(a == b == c) check = false;
    else if(a >= b and a >= c){
        max = 'A';
        if((b+c) != a) check = false;
    }
    else if(b >= a and b  >= c){
        max = 'B';
        if((a+c) != b) check = false;
    }
    else if(c >= a and c >= b){
        max = 'C';
        if((b+a) != c) check = false;
    }
    // cout<<max<<" "<<check<<" ";
    if(a == 0 || b == 0 || c == 0)
        max = s[0];

    bool pos = false;
    if(s[0] == max) pos = true;

    for(int i = 0; i < s.length(); i++){
        if(s[i] == max){
            if(pos) count++;
            else count--;
        }
        else{
           if(pos) count--;
           else count++;
        }
        // cout<<count<<"\n";
        if(count < 0){
            check = false;
            break;
        }
    }

    if(check) cout<<"YES\n";
    else cout<<"NO\n";
 
}
 
int main(){ 

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#endif

    ll t = 1;   
    scanf("%lld", &t);

    ll mod = 1000000007;

    while(t--){
        solve();
    }

    return 0;

}

