#include <bits/stdc++.h>
using namespace std;
#define l1 long long int 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test l1 t;cin>>t;while(t--)
// Function to check 
// if parentheses are balanced 
bool isBalanced(string exp) 
{ 
  
    // Initialising Variables 
    bool flag = true; 
    l1 count = 0; 
  
    // Traversing the Expression 
    for (l1 i = 0; i < exp.length(); i++) { 
  
        if (exp[i] == '(') { 
            count++; 
        } 
        else { 
  
            // It is a closing parenthesis 
            count--; 
        } 
        if (count < 0) { 
  
            // This means there are 
            // more Closing parenthesis 
            // than opening ones 
            flag = false; 
            break; 
        } 
    } 
  
    // If count is not zero, 
    // It means there are 
    // more opening parenthesis 
    if (count != 0) { 
        flag = false; 
    } 
  
    return flag; 
}

int main()
{
    fast
    test
    {
        l1 i,l;
        string str,str1="",str2="";
        cin>>str;
        l=str.size();
        l1 a=0,b=0,c=0;
        for(i=0;i<l;i++)
        {
            if(str[i]=='A')
            {
                a++;
            }
            if(str[i]=='B')
            {
                b++;
            }
            if(str[i]=='C')
            {
                c++;
            }
        }
        l1 arr[3];
        arr[0]=a;arr[1]=b;arr[2]=c;
        sort(arr,arr+3);
        char temp=NULL;
        if(arr[2]==a)
        {
            temp='A';
        }
        else
        {
            if(arr[2]==b)
            {
                temp='B';
            }
            else
            {
                temp='C';
            }
        }
        for(i=0;i<l;i++)
        {
            if(str[i]==temp)
            {
                str1+="(";
                str2+=")";
            }
            else
            {
                str1+=")";
                str2+="(";
            }
        }
        if(isBalanced(str1) || isBalanced(str2))
        {
            cout<<"YES\n";
        }
        else
        {
            cout<<"NO\n";
        }
    }
}