#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define M 1000000007
#define make_unique(vec) vec.erase(unique(all(vec)), vec.end())
#define itc int t;cin>>t;while(t--)
#define SET(a, b) memset(a, b, sizeof(a))
#define forn(i,a, n) for (int i = a; i < (int)(n); i++)
#define tcs(n) for (int i = 1; i <= (int)(n); i++)
#define ll long long
#define ld long double
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef unsigned long long ubint;

void solve();

int main()
{
    fio;
    int tc=1;
    cin >> tc;
    tcs(tc)
    {
        solve();
    }
}

void solve()
{
    ll n, i;
    string s, ss;
    cin >> s;
    map<char, int> m;
    n = s.size();
    for (i = 0; i < s.size(); i++)
    {
        m[s[i]]++;
    }
    if (max({m['A'], m['B'], m['C']}) * 2 != n)
    {
        cout << "NO" << endl;
        return;
    }
    char c, t;
    if (m['A'] > m['B'] && m['A'] > m['C'])
        c = 'A';
    else if (m['B'] > m['C'])
        c = 'B';
    else
        c = 'C';
    for (i = 0; i < n; i++)
    {
        if (c == s[0])
        {
            if (c == s[i])
                ss += '(';
            else
                ss += ')';
        }
        else
        {
            if (c == s[i])
                ss += ')';
            else
                ss += '(';
        }
    }
    int y = 0;
    for (i = 0; i < n; i++)
    {
        if (ss[i] == '(')
            y++;
        else
            y--;
        if (y < 0)
            break;
    }
    // cout<<ss<<endl;
    // DD(c,y)
    if (y < 0)
    {
        cout << "NO" << endl;
    }
    else
    {
        cout << "YES" << endl;
    }
    
        // no else yes
}
