#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "../../debug.h"
#else
#define DEB(...)
#endif
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl '\n'
#define all(a) (a).begin(),(a).end()
#define sz(a) ((int)(a).size())
#define forn(i,n) for(int i=0; i<(n); i++)
#define forne(i,n) for(int i=0; i<(n) || (cout << endl,0) ; i++) 
#define fora(i,a,b) for(int i=a; i<=(b); i++)
#define ford(i,a,b) for(int i=a; i>=(b); i--)
#define muniq(x) sort(all(x)), x.erase(unique(all(x)), x.end())
template<class T> bool mmin(T& a, const T& b) { return b<a?a=b,1:0; }
template<class T> bool mmax(T& a, const T& b) { return a<b?a=b,1:0; }
template<class T> void puts(T a) { cout << a << ' '; }
template<class T> void put(T a) { cout << a << endl; }
template<class T> void put(T ita, T itb) { while(ita!=itb) puts(*ita++); cout << endl; }
void yesno(bool c) { put(c?"YES":"NO"); }
void yes() { yesno(true); } void no() { yesno(false); }
void imp() { put("-1"); }
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

void solve() {
    string a;
    cin >> a;
    int n = a.length();

    string b(n, ' ');
    if(a[0]==a[n-1]) return no();
    forn(i,n) {
        if(a[i]==a[0])
            b[i] = '(';
        else if(a[i]==a[n-1]) 
            b[i] = ')';
    }
    vi pos(n);
    forn(i,n) if(b[i]==' ') pos[i] = 1;
    forn(i,n) if(pos[i]) b[i] = '(';
    int cnt = 0;
    int ok = 1;
    forn(i,n) {
        cnt += b[i]=='(' ? 1 : -1;
        if(cnt<0) ok = 0;
    }
    if(cnt==0 && ok) {
        return yes();
//        return put(b);
    }
    forn(i,n) if(pos[i]) b[i] = ')';    
    ok = 1;
    cnt = 0;
    forn(i,n) {
        cnt += b[i]=='(' ? 1 : -1;
        if(cnt<0) ok = 0;
    }
    if(cnt==0 && ok) {
        return yes();
//        return put(b);
    } else return no();

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tc = 1; cin >> tc;
    while(tc--) solve();

    return 0;
}
