#include <bits/stdc++.h>

using namespace std;

bool solve() {
  string s;
  cin >> s;
  vector<int> d(3);
  int x = s[0] - 'A';
  int y = s.back() - 'A';
  if (x == y)
    return false;
  d[x] = 1; d[y] = -1;
  if (count(s.begin(), s.end(), 'A' + x) == s.length() / 2)
    d[3 ^ x ^ y] = -1;
  else
    d[3 ^ x ^ y] = 1;
  int bal = 0;
  for (char c : s) {
    bal += d[c - 'A'];
    if (bal < 0) return false;
  }
  return bal == 0;
}

int main() {
  int t; cin >> t;
  while (t--) {
    cout << (solve() ? "YES\n" : "NO\n");
  }
}

for _ in range(int(input())):
    n, U, R, D, L = map(int, input().split())
    for mask in range(16):
        rU, rR, rD, rL = U, R, D, L
        if mask & 1:
            rU -= 1
            rL -= 1
        if mask & 2:
            rL -= 1
            rD -= 1
        if mask & 4:
            rD -= 1
            rR -= 1
        if mask & 8:
            rR -= 1
            rU -= 1
        if min(rU, rR, rD, rL) >= 0 and max(rU, rR, rD, rL) <= n - 2:
            print("YES")
            break
    else:
        print("NO")

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int calc(const vector<int> &a, const vector<int> &b){
    int n = a.size();
    int m = b.size();
    vector<int> c(n), res;
    vector<int> su(n + 1);
    int r = m - 1;
    for (int i = n - 1; i >= 0; --i){
        su[i] = su[i + 1];
        while (r >= 0 && b[r] > a[i]) --r;
        if (r >= 0 && b[r] == a[i]) ++su[i];
    }
    int ans = 0;
    int j = 0;
    r = 0;
    forn(l, m){
        while (j < n && a[j] <= b[l] + j) ++j;
        while (r < m && b[r] - b[l] < j) ++r;
        ans = max(ans, r - l + su[j]);
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    forn(_, t){
        int n, m;
        scanf("%d%d", &n, &m);
        vector<int> a(n), b(m);
        forn(i, n) scanf("%d", &a[i]);
        forn(i, m) scanf("%d", &b[i]);
        vector<int> al, bl, ar, br;
        forn(i, n){
            if (a[i] < 0) al.push_back(-a[i]);
            else ar.push_back(a[i]);
        }
        forn(i, m){
            if (b[i] < 0) bl.push_back(-b[i]);
            else br.push_back(b[i]);
        }
        reverse(al.begin(), al.end());
        reverse(bl.begin(), bl.end());
        printf("%d\n", calc(al, bl) + calc(ar, br));
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())

const int N = 505;

int n;
int a[N][N];
int c[2 * N];
vector<pair<int, int>> e;

int calc(vector<int> ls) {
  if (sz(ls) == 1)
    return ls[0];
  
  int res = -1;
  for (int u : ls)
    res = max(res, a[ls[0]][u]);
  
  vector<vector<int>> ch;
  ch.push_back({ls[0]});
  for (int i = 1; i < sz(ls); ++i) {
    int v = ls[i];
    int group = -1;
    for (int j = 0; j < sz(ch); ++j) {
      if (a[v][ch[j][0]] != res) {
        group = j;
        break;
      }
    }
    if (group == -1) {
      group = sz(ch);
      ch.push_back({});
    }
    ch[group].push_back(v);
  }
  
  int v = n++;
  c[v] = res;
  for (int i = 0; i < sz(ch); ++i) {
    int u = calc(ch[i]);
    e.emplace_back(u, v);
  }
  return v;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      cin >> a[i][j];
  for (int i = 0; i < n; ++i)
    c[i] = a[i][i];
  vector<int> ls(n);
  iota(ls.begin(), ls.end(), 0);
  int root = calc(ls);
  cout << n << '\n';
  for (int i = 0; i < n; ++i)
    cout << c[i] << ' ';
  cout << '\n' << root + 1 << '\n';
  for (auto it : e)
    cout << it.first + 1 << ' ' << it.second + 1 << '\n';
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef pair<int, int> pt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    map<pt, int> allEdges;
    set<pt> difPairs, eqPairs;
    
    fore (q, 0, m) {
        char tp; cin >> tp;
        if (tp == '+') {
            int u, v;
            char c;
            cin >> u >> v >> c;
            
            if (allEdges.count({v, u})) {
                if (allEdges[{v, u}] == c)
                    eqPairs.emplace(min(u, v), max(u, v));
                else
                    difPairs.emplace(min(u, v), max(u, v));
            }
            allEdges[{u, v}] = c;
            
        } else if (tp == '-') {
            int u, v;
            cin >> u >> v;
            if (eqPairs.count({min(u, v), max(u, v)}))
                eqPairs.erase({min(u, v), max(u, v)});
            if (difPairs.count({min(u, v), max(u, v)}))
                difPairs.erase({min(u, v), max(u, v)});
            
            allEdges.erase({u, v});
        } else {
            int k;
            cin >> k;
            
            bool hasAns = !eqPairs.empty();
            if (k & 1)
                hasAns |= !difPairs.empty();
            cout << (hasAns ? "YES" : "NO") << '\n';
        }
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300043;

int n, m;
set<int> g[N];
set<int> g2[N];

vector<int> res;

void euler(int x)
{
    while(!g2[x].empty())
    {
        int y = *g2[x].begin();
        g2[x].erase(y);
        g2[y].erase(x);
        euler(y);
    }
    res.push_back(x);
}

bool check(int c)
{
    for(int i = 1; i <= n; i++)
        g2[i] = g[i];
    res = vector<int>();
    euler(c);
    int curm = 0;
    for(int i = 1; i <= n; i++)
        curm += g[i].size();
    for(int i = 1; i <= n; i++)
        g2[i] = g[i];
    for(int i = 1; i < res.size(); i++)
    {
        int x = res[i - 1];
        int y = res[i];
        if(g2[x].count(y) != 1)
            return false;
        g2[x].erase(y);
        g2[y].erase(x);
    }
    return curm / 2 + 1 == res.size();    
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        g[x].insert(y);
        g[y].insert(x);
    }
    for(int i = 1; i <= n; i++)
    {
        set<int> pr = g[i];
        set<int> diff;
        for(auto x : pr)
            if(g[x].size() % 2 == 1)
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
        if(check(i))
        {
            res.push_back(-1);
            for(auto x : diff)
            {
                res.push_back(x);
                res.push_back(i);
            }
            printf("%d\n", res.size());
            for(auto x : res) printf("%d ", x);
            puts("");
            exit(0);
        }
        for(auto x : pr)
        {
            if(g[i].count(x))
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
            else
            {
                g[i].insert(x);
                g[x].insert(i);
                diff.erase(x);
            }
            if(check(i))
            {
                res.push_back(-1);
                for(auto x : diff)
                {
                    res.push_back(x);
                    res.push_back(i);
                }
                printf("%d\n", res.size());
                for(auto x : res) printf("%d ", x);
                puts("");
                exit(0);
            }
            if(g[i].count(x))
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
            else
            {
                g[i].insert(x);
                g[x].insert(i);
                diff.erase(x);
            }
        }
        for(auto x : diff)
        {
            g[i].insert(x);
            g[x].insert(i);
        }
    }
    puts("0");
}