#include <bits/stdc++.h>
// template starts
using namespace std;
 
typedef long long int lli;
 
// template ends

lli ceil(lli a, lli b)
{
    
    if (a%b==0)
       return a/b;
    else return a/b+1;
}




int main()
{	

	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
    		string a;
    		cin>>a;
    		int n= a.size();
    		
    		if(a[0]==a[n-1])
    		{
    			cout<<"No\n";
    			continue;
			}
			map <char, char> mp;
			mp.insert({a[0], '('});
			mp.insert({a[n-1],')'});
			char ch;
			if(a[0]+a[n-1]==131)
			ch='C';
			else if(a[0]+a[n-1]==133)
			ch='A';
			
			else 
			ch='B';
			
			vector<char> b1(n, ' '), b2(n, ' ');
			for(int i=0; i<n; i++)
			{
				if(a[i]!=ch)
				{
					b1[i]= mp[a[i]];
					b2[i]=mp[a[i]];
				}
				else
				{
					b1[i]='(';
					b2[i]=')';
				}
				
			}
			int cnt1=0, flag1=-1;
			
			/*
			for(auto x:b1)
			cout<<x;
			cout<<"\n";
			for(auto x:b2)
			cout<< x;
			cout<<"\n";
			*/
			
			for(int i=0; i<n; i++)
			{
				if(b1[i]=='(')
				{
					cnt1++;
				}else if(b1[i]==')'&& cnt1>0)
				{
					cnt1--;
				}
				else
				{
					flag1=1;
					break;
				}
			}
			if(cnt1==0&&flag1!=1)
			flag1=0;
			int cnt2=0, flag2=-1;
			
			for(int i=0; i<n; i++)
			{
				if(b2[i]=='(')
				{
					cnt2++;
				}else if(b2[i]==')'&& cnt2>0)
				{
					cnt2--;
				}
				else
				{
					flag2=1;
					break;
				}
			}
			if(cnt2==0&&flag2!=1)
			flag2=0;
			if(flag1==0||flag2==0)
			cout<<"Yes\n";
			else
			cout<<"No\n";
			
	}
    
    
	return 0;
}