#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<stack>
using namespace std;
stack<int>q;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		string str;
		cin>>str;
		bool flag = false;
		for(int i=1;i<=2;i++){
			if(flag) break;
			for(int j=1;j<=2;j++){
				if(flag)break;
				for(int k=1;k<=2;k++){
					if(flag)break;
					while(!q.empty())q.pop();
					flag = true;
					for(int s=0;s<str.length();s++){
						int now;
						if(str[s]=='A')now = i;
						else if(str[s]=='B')now = j;
						else if(str[s]=='C')now = k;
						if(now==2&&!q.empty()){
							q.pop();
						}
						else if(now==1){
							q.push(1); 
						}
						else {
							flag = false ;
							break;
						}
					}
					if(!q.empty())flag = false;
				}
			}
		}
		if(flag)printf("YES\n");
		else printf("NO\n");
	}
} 