#include<fstream>
#include<list>
#include<string>
#define ST -1
#define DR 1

using namespace std;

class turing{
list<char> banda;
list<char>::iterator capat;

public:
	turing(char *ch){
		banda.push_back('B');
		while ((*ch)!='\0'){banda.push_back(*ch);

		ch++;}
		banda.push_back('B');
		capat=banda.begin();
		capat++;

	}
	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 retur(){capat=banda.begin(); capat++;}
	
	int abc(){

	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;}