#include <bits/stdc++.h> 
using namespace std;
#define int long long int 
#define float  long double
#define pb push_back
#define mp make_pair
#define pii pair<int,int>  
#define vi vector<int>
#define mii map<int,int>
#define setbits(n) __builtin_popcount(n)
#define endl "\n"
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int mod = 1e9+7;
const int  N = 2e5+5;
int fact[N],inv[N];

int gcd ( int a, int b)
{
    if(b==0)
    return a;
    return gcd(b,a%b);
}

int lcm(int a, int b)
{
    return (a*b)/gcd(a,b);
}

int power(int a, int b, int p)
{
    if(a==0)
    return 0;
    int res = 1;
    a%=p;
    while(b>0)
    {
        if(b%2)
        res= (res*a)%p;
        a = (a*a)%p;
        b = b/2;
        
    }
    return res; 
}
void factorials()
{
    fact[0] = 1;
    inv[0] = 1;
    for(int i=1;i<N;i++)
    fact[i] = (i%mod * fact[i-1])%mod;
    for(int i=1;i<N;i++)
    inv[i] = power(fact[i],mod-2,mod);
}

bool check (string s)
{
	stack<int> st;
	int n = s.size();
	int one = 1;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='(')
		st.push(one);
		else if(st.empty())
		return false;
		else
		st.pop();
	}
	if(st.empty())
	return true;
	return false; 
}

string make (string s,char a, char b, char c)
{
	int n = s.size();
	for(int i=0;i<n;i++)
	{
		if(s[i]=='A')
		s[i] = a;
		if(s[i]=='B')
		s[i]  = b;
		if(s[i]=='C')
		s[i] = c;
	}
	return s;
}


void solve()
{
    
    string s; cin>>s;
    char o = '(', c = ')';
    string x = "(())(";
    
    if(check(make(s,o,o,o))) { yes return; }
     if(check(make(s,o,o,c))) { yes return; }
       if(check(make(s,o,c,o))) { yes return; }
        if(check(make(s,o,c,c))) { yes return; }
         if(check(make(s,c,o,o))) { yes return; }
          if(check(make(s,c,o,c))) { yes return; }
           if(check(make(s,c,c,o))) { yes return; }
            if(check(make(s,c,c,c))) { yes return; }    
            
            no return; 
    
    
    
}

int32_t main()
{

    IOS
    
      int t; cin>>t; 
      while(t--)
      {
         solve();
      }
}
         

