#include <bits/stdc++.h>
using namespace std;
char a,b;
int main()
{
    int t,w;
    cin>>t;
   for(int j=0;j<t;j++){
   	
        char s[1000];
        scanf("%s",s);
        int  flag=1,flag2=0,f=0;
        int sum=0;
        int len=strlen(s);
        a=s[0];
        b=s[len-1];
        if(a==b)
        {
            puts("NO");
            continue;
        }
        for(int i=0;i<len;++i)
		{
			if(s[i]!=a&&s[i]!=b)
			{
				s[i]='U';
			
			}
		};
        for(int i=0;i<len;++i)
        {
            if(s[i]==a&&sum>=0)
            {
            	sum++;
			}
            else if(s[i]==a&&sum<0)
            {
            	flag=0;
			}
            if(s[i]==b||s[i]=='U'&&sum)
            {
            	sum--;
			}
            else if((s[i]==b||s[i]=='U')&&sum<=0)
            {
            	flag=0;
			}
        }
        if(flag&&sum==0)flag2=1;
        sum=0;
        flag=1;
        for(int i=0;i<len;++i)
        {
            if((s[i]==a||s[i]=='U')&&sum>=0)
            {
            	sum++;
			}
            else if((s[i]==a||s[i]=='U')&&sum<0)
            {
            	flag=0;
			}
            if(s[i]==b&&sum){
            	sum--;
			}
            else if(s[i]==b&&sum<=0)
            {
            	flag=0;
			}
        }
        if(flag&&sum==0)
        {
        	puts("YES");
        	continue;
		}
        if(flag2){
        	puts("YES");
        	continue ;
		}
        else{
        	puts("NO");
		}
   }
    
    return 0;}