/*
Autor: Grigore Alexandru Constantin, grupa 232

Algoritmul simuleaza o masina Turing care verifica daca un cuvant introdus de
la tastatura apartine limbajului a^m b^n c^p, cu m=n sau n=p.
Algoritmul propriu-zis (excluzand citirea) foloseste doar o lista dublu 
inlantuita si o singura variabila ajutatoare.

Pentru o afisare mai detaliata se pot decomenta comentariile facute cu "//".
*/


#include <cstdlib>
#include <list>
#include <fstream>
#include <iostream>

using namespace std;

void afiseaza(list<char> v)
{ list<char>::iterator pv;
  cout<<endl<<"Continutul benzii: ";
  for(pv=v.begin(); pv!=v.end(); pv++)
 		cout<<*pv;
 	cout<<endl<<endl;
}

int main()
{   int n, i, j, k;
    bool bun;
    char cuv[1001];
    
    ifstream f("tm.in");
    f>>n;
    ofstream g("tm.out");
    for(i=1; i<=n; i++)
    { 
      f>>cuv;
      list<char> v;
      for(j=0; j<strlen(cuv); j++)
           v.push_back(cuv[j]);
      v.push_back('X');
      afiseaza(v);
     
     
      k=1;
      list<char>::iterator pv;
      bun=true;
      for(pv=v.begin(); pv!=v.end(); pv++)
        if(k==1 && *pv=='b') k=2;
          else if( (k==2 || k==1) && *pv=='c') k=3;
              else if(k==2 && *pv=='a') bun=false;
                       else if(k==3 && (*pv=='b' || *pv=='a')) bun=false;
      if(!bun){ g<<"NU"<<endl;
                continue;
                }
      
      pv=v.begin();
      int stare=0;
    
      bun=false;
      do{ 
        if(stare==0)
             if(*pv=='a') {/*marchez un a, trec la pozitia urmatoare si schimb starea 
			                (in starea 1 trebuie sa mai existe un b) */
                          *pv='A';
                          pv++;
                          stare=1;
                          }
                else if(*pv=='b'){/*inseamna ca nu exista a, dar exista b, si se trece mai departe
                                    inseamna ca |b|>|a| */
                                  // cout<<"|a|<|b|"<<endl<<endl;
                                   break;
                                 }
                           else {/*nu exista nici a nici b */
                                 bun=true; 
                                 g<<"DA"<<endl;
                                 break;
                                 }
       
        if(stare==1)
            if(*pv=='a' || *pv=='B')  /*caut un b, deci sar peste a si B */ 
                                      pv++;
                else if(*pv=='b'){/*acum |a|==|b| si trebuie sa ma intorc*/
                                 *pv='B';
                                 stare=2;
                                 pv--;
                                  }
                          else if(*pv=='c') {/*inseamna ca |a|>|b|, si trec mai departe */
                                            // cout<<"|a|>|b|"<<endl<<endl;
                                             break;
                                             }
                                     else if(*pv=='X') {//cout<<"|a|>|b|"<<endl<<endl;
                                                         break;
                                                         }
                                           
                                           
        if(stare==2)
            if(*pv!='A')  /*sar peste toate literele pana la ultimul a marcat (A) */
                         pv--;
                else {/*am ajuns la ultimul a marcat (A), deci citesc ce urmeaza dupa el */
                      pv++;
                      if(*pv=='a') {/*am gasit un a nou, il marchez si trec in starea 1 
                                      din nou, pentru a cauta urmatorul b nemarcat */
                                   *pv='A';
                                    stare=1;
                                    pv++;
                                   }
                         else if(*pv=='B') {/*nu mai exista a nemarcat, deci trebuie 
                                            sa verificam daca mai exista vreun b nemarcat; 
                                            schimbam starea in starea 3 */
                                           stare=3;
                                           pv++;
                                           }
					}
        if(stare==3)
              if(*pv=='B') pv++;
                 else if(*pv=='c' || *pv=='X') 
                                   {g<<"DA"<<endl;
                                    bun=true;
                                    break;
                                   }   
                             else{ /*inseamna ca |b|>|a| */ 
                                   //cout<<"|a|<|b|"<<endl<<endl;
                                   break;
                                 }
                         
                      
       // afiseaza(v);
           }while(1);
           
  /*daca s-a ajuns aici inseamna ca |a|!=|b| */
  
  /*se demarcheaza toti B */
  
  if(!bun)
  {pv=v.begin();
    while(*pv!='X')
     {if(*pv=='A' || *pv=='a') /*sterg toti a (sau A) din lista */ 
              { v.pop_front();
               pv=v.begin();
              }
         else if(*pv=='B') {*pv='b';
                            pv++;
                            }
             else break;
      }
      
       
  //afiseaza(v); 
   
   /*verific daca |b|==|c| */
   pv=v.begin();
   stare=0;
    do{ 
        if(stare==0)
             if(*pv=='b') {/*marchez un b, trec la pozitia urmatoare si schimb
                            starea (in starea 1 trebuie sa mai existe un c) */ 
                          *pv='B';
                          pv++;
                          stare=1;
                          }
                else if(*pv=='c'){/*inseamna ca nu exista b, dar exista c, si este respins cuvantul
                                   inseamna ca |c|>|b| */  
                                   g<<"NU"<<endl;
                                   break;
                                 }
                           else {/*nu exista nici b nici c */
                                 cout<<"Cuvantul este acceptat (|b|=|c|)."<<endl<<endl; 
                                 g<<"DA"<<endl;
                                 break;
                                 }
       
       
        if(stare==1)
            if(*pv=='b' || *pv=='C')  /*caut un c, deci sar peste b si C */
                                      pv++;
                else if(*pv=='c'){/*acum |b|==|c| si trebuie sa ma intorc */
                                 *pv='C';
                                 stare=2;
                                 pv--;
                                  }
                          else if(*pv=='X') {/*inseamna ca |b|>|c|, si resping cuvantul */
                                             g<<"NU"<<endl;
                                             break;
                                             }
                                           
                                           
        if(stare==2)
            if(*pv!='B')  /*sar peste toate literele pana la ultimul b marcat (B)*/
                         pv--;
                else {/*am ajuns la ultimul b marcat (B), deci citesc ce urmeaza dupa el */
                      pv++;
                      if(*pv=='b') {/*am gasit un b nou, il marchez si trec in starea 1 
                                     din nou, pentru a cauta urmatorul c nemarcat */
                                   *pv='B';
                                    stare=1;
                                    pv++;
                                   }
                         else if(*pv=='C') {/*nu mai exista b nemarcat, deci 
                                             trebuie sa verificam daca mai exista 
                                             vreun c nemarcat; schimbam starea in starea 3 */
                                           stare=3;
                                           pv++;
                                           }
					}
        if(stare==3)
              if(*pv=='C') pv++;
                 else if(*pv=='X') {
                                   g<<"DA"<<endl;
                                   break;
                                   }   
                             else{ /*inseamna ca |c|>|b| si cuvantul este respins */  
                                   
                                   g<<"NU"<<endl;
                                   break;
                                 }
                         
                      
       // afiseaza(v);
           }while(1);
       }
   }
   
   f.close();
   g.close();
    
    return 0;
}