#include<bits/stdc++.h>

using namespace std;



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	
	int t;
	cin>>t;
	string a;
	while(t--){
		cin>>a;
		int sz = a.size();
		if(a[0] == a[sz-1])
			cout<<"NO\n";
		else{
			char open = a[0] , close = a[sz-1];
			int cur = 0;
			//last is open
			for(int i=0;i<a.size();i++){
				if(a[i] == open)
					cur++;
				else if(a[i] == close){
					cur--;
					if(cur < 0)
						break;
				}
				else
					cur++;
			}
			if(cur == 0)
				cout<<"YES\n";
			else{
				cur = 0;
				for(int i=0;i<a.size();i++){
					if(a[i] == open)
						cur++;
					else{
						cur--;
						if(cur < 0)
							break;
					}
				}
				if(cur == 0)
					cout<<"YES\n";
				else
					cout<<"NO\n";
			}
		}
	}

	return 0;
	
}