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


int main() {
    int t ;
    cin>>t;
    while(t--){
        string S;
        cin>>S;
        stack<char> St;
        char start = S[0];
        char end = S[S.length()-1];
        int a=0 , b=0 ,c=0;
        if(start==end){
            cout<<"No"<<endl;
            continue;
        }
        for(int i =0 ; i<S.length();i++){
            if(S[i]==start){
                a++;
            }
            if(S[i]==end){
                b++;
            }
        }
        char sec = (a>b)?end:start;
        for(int i =0 ; i<S.length();i++){
            if(S[i]!=start && (S[i]!=end)){
                S[i]=sec;
            }
        }
        //cout<<S<<endl;
        for(int i =0 ; i<S.length();i++){
            if(St.size()==0){
                St.push(S[i]);
            }
            else if(St.top()==start && (S[i]==end)){
                //cout<<2<<endl;
                St.pop();
            }
            else{
                //cout<<4<<endl;
                St.push(S[i]);
            }
        }
        if(St.size()==0) cout<<"Yes";
        else cout<<"No";
        cout<<endl;
    }
}