#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl "\n"
#define mod 1000000007
// vector<int>x{-1,-1,-1,0,1,1,1,0};
// vector<int>y{-1,0,1,1,1,0,-1,-1};
// vector<pair<int,int>>v;
// int a,b;
// set<int>s;
// #define mod 1
//  vector<int>v1,v2;
// int dp[100001];
// vector<int>v;
// int ans=0;
// map<int,int>m;
// set<pair<int,int>>s;
// vector<int>adj[100001];
//   vector<bool>vis(100001,false);
// int dis[100001];
// string s1,s2;
// vector<int>v;
// vector<int>p;
// int power(int x,int y)
// { int temp;
//   if(y==0)
//     return 1;
//   temp=power(x,y/2)%mod;
//   if(y%2==0)
//     return (temp%mod*temp%mod)%mod;
//   else
//     return ((x%mod)*((temp%mod*temp%mod)%mod))%mod;
// }
vector<int>temp;
void seive(int n)
{
  vector<bool>vis(n+1,false);
  for(int i=4;i<=n;i+=2)
    vis[i]=true;
  for(int i=3;i*i<n;i++)
  {
    if(vis[i]==true)
      continue;
    for(int j=i*i;j<n;j+=i)
    {
      vis[j]=true;
    }
  }
  for(int i=2;i<=n;i++)
  {
    if(vis[i]==false)
      { 
        temp.push_back(i*i);
      }
  }
}
bool check(vector<char>&v,int n)
{
  stack<char>s;
  for(int i=0;i<n;i++)
  {
    if(v[i]=='(')
      s.push('(');
    else
    {
      if(s.empty())
        return false;
      s.pop();
    }
  }
  if(s.empty())
    return true;
  return false;
}
void solve()
{ 
  string s;
  cin>>s;
  int n=s.size();
  if(s[0]==s[n-1])
  {
    cout<<"NO"<<endl;
    return;
  }
  char a=s[0];
  char b=s[n-1];
  vector<char>v1,v2;
  for(int i=0;i<n;i++)
  {
    if(s[i]==a)
      v1.push_back('(');
    else if(s[i]==b)
      v1.push_back(')');
    else
      v1.push_back(')');
  }
  for(int i=0;i<n;i++)
  {
    if(s[i]==a)
      v2.push_back('(');
    else if(s[i]==b)
      v2.push_back(')');
    else
      v2.push_back('(');
  }
  bool x=check(v1,n)||check(v2,n);
  if(x)
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
}
signed main()
{   

  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
      #ifndef ONLINE_JUDGE
  freopen("input1.txt","r",stdin);
  freopen("output1.txt","w",stdout);
      #endif
  //seive(1e6+1);
  int t;
  cin>>t;
  //t=1;
  for(int i=1;i<=t;i++)
  { 
    solve();
  }
    return 0;     
}