#include<bits/stdc++.h>
using namespace std;
 bool check1(string s){
        char temp=s[0];
        stack<char> st;
        st.push('(');
        for(int i=1;i<s.size();i++){
            if(s[i]!=temp){
                if(!st.empty()) st.pop();
                else return false;
            }
            else st.push('(');
        }
        if(st.empty()) return true;
        else return false;
    }
 bool check2(string s){
        int n=s.size();
        char temp=s[n-1];
        stack<char> st;
        for(int i=0;i<s.size();i++){
            if(st.empty() && s[i]==temp){
                return false;
            }
            else if(s[i]==temp){
                st.pop();
            }
            else{
                st.push('(');
            }
        }
        if(st.empty()) return true;
        else return false;
    }
   
int main(){
    long long int t;
    cin>>t;
    while(t--){
        long long int n,k,flag=0,cnt1=0,cnt2=0,cnt3=0;
        string s;
        cin>>s;
        n=s.size();
        if(check1(s) || check2(s)){
            cout<<"YES"<<"\n";
        }
        else cout<<"NO"<<"\n";
    }
}