//#include<iostream>
#include<fstream>
#include<list>
#include<set>
#include<string>
#include <algorithm>
#define ST -1
#define DR 1
#define STAY 0
using namespace std;
/*
struct triplet{
	char stare;
	char scris;
	int stdr;
	triplet(){stare='E';
	scris='X';
	stdr=STAY;
	}
};*/
class turing{
list<char> banda;
list<char>::iterator capat;
//set<char> stari;
//set<char> alfabet;
//triplet delta[255][255];
//char stare;
//char stare_err;
public:
	turing(char *ch){
		banda.push_back('B');//alfabet.insert('B');
		while ((*ch)!='\0'){banda.push_back(*ch);
		//alfabet.insert(*ch);
		ch++;}
		banda.push_back('B');
		capat=banda.begin();
		capat++;
		//stare='0';stari.insert('0');
		//stare_err='E';stari.insert('E');
	}
	friend ostream &operator <<(ostream &x,turing &t){
		list<char>::iterator parcurg;
		for (parcurg=t.banda.begin();parcurg!=t.banda.end();parcurg++)
			x<<*parcurg;
		x<<"\n";
		for (parcurg=t.banda.begin();parcurg!=t.capat;parcurg++)
			x<<" ";
		x<<"^\n";
		return x;
	}
	void move(int x){
		if ((x==ST)&&(capat!=banda.begin()))capat--;
		if ((x==DR)&&(capat!=banda.end()))capat++;
	}
	//void alf(){set<char>::iterator it=alfabet.begin(); while (it != alfabet.end()) {cout<<*it;it++;}cout<<"\n";}
	//void str(){set<char>::iterator it=stari.begin(); while (it != stari.end()) {cout<<*it;it++;}cout<<"\n";}
	/*void addRule(char a,char b, char c, char d, int e){
	triplet t;
	t.stare=c;
	t.scris=d;
	t.stdr=e;
	delta[a][b]=t;
	}*/
	void retur(){capat=banda.begin(); capat++;}
	
	int abc(){
		//retur();
	if (*capat=='B')return 1;
	while (*capat=='a') move(DR);
	if (*capat=='B')return 1;
	while (*capat=='b') move(DR);
	if (*capat=='B')return 1; else if (*capat=='a')return 0;
	while (*capat=='c') move(DR);
	if (*capat=='B')return 1; else if (*capat=='b'||*capat=='a')return 0;
	return 0;
	}
	
	int abc2(){
	retur();
	while (*capat=='a'){*capat='x';
	move(DR);
	while (*capat=='a'||*capat=='y') move(DR);
	
	if (*capat=='b') {*capat='y';
	
	while (*capat!='x') move(ST);
	
	move(DR);
	
	}
	}
	if (*capat=='y') {while (*capat=='y') {*capat='b'; move(DR);} if (*capat=='c'||*capat=='B') return 1;else {while (*capat!='x') move(ST); move(DR);}}
	
	else if (*capat=='B'||*capat=='c')
		{move(ST);
	while (*capat=='y'){*capat='b';move(ST);}
	move(DR);
		}
			
		//***********
		
		while (*capat=='b'){*capat='y';
	move(DR);
	while (*capat=='b'||*capat=='z') move(DR);
	
	if (*capat=='c') {*capat='z';
	
	while (*capat!='y') move(ST);
	
	move(DR);
	
	}}
		
		if (*capat=='B') return 0;
		else if (*capat=='z')
			while (*capat=='z')move(DR);
		if (*capat=='B') return 1;
			return 0;
		
		
	
	}
};

int main(){
	ifstream f("tm.in");
	ofstream g("tm.out");
	char str[1001];
	int n;
	f>>n;
	turing *M;
	for (int i=1;i<=n;i++)
		{f>>str;
	M=new turing(str);
	if ((*M).abc()==0){g<<"NU\n";}
	else{if ((*M).abc2()==1) {g<<"DA\n";}
	else {g<<"NU\n";
	}
	}
delete M;
		}
return 0;}

/*

	//verificare a*b*c*
	M.addRule('0','a','a','A',DR);
	M.addRule('a','a','a','A',DR);
	M.addRule('a','b','b','P',DR);
	M.addRule('a','c','c','C',DR);
	
	M.addRule('0','b','b','P',DR);
	M.addRule('b','b','b','P',DR);
	M.addRule('b','c','c','C',DR);
	M.addRule('b','a','a','E',DR);//stare eroare
	
	M.addRule('0','c','c','C',DR);
	
	
	

*/