#include <iostream>
#include <cstring>

/*
 * Exercise 0
 */

const int MAX_DICT_SIZE      =  128,
		  MAX_DICT_ITEM_SIZE =  100,
		  MAX_SRC_SIZE       = 1024,
		  MAX_RES_SIZE       = 2048;

bool mustAddSpaceBefore(char ch) {
	return ch == '-' || ch == '+' || ch == '*' || ch == '/' || ch == '^' || ch == '=' || ch == '(';
}

bool mustAddSpaceAfter(char ch) {
	return ch == '.' || ch == ',' || ch == '?' || ch == '!' || ch == ';' || ch == ':' ||
			(mustAddSpaceBefore(ch) && ch != '(');
} 

bool dictItemInStr(int srcSize, char src[MAX_SRC_SIZE], char dictItem[MAX_DICT_ITEM_SIZE], int startInd) {
	for (int i = 0; i + startInd < srcSize && dictItem[i] != '-'; i++) {
		if (src[i + startInd] != dictItem[i])
			return false;
	}
	return true;
}

void autoCorrect(int srcSize, char src[MAX_SRC_SIZE], int dictSize, char dict[MAX_DICT_SIZE][MAX_DICT_ITEM_SIZE], char res[MAX_RES_SIZE]) {
	char firstLetDict[MAX_DICT_SIZE];
	for (int i = 0; i < dictSize; i++)
		firstLetDict[i] = dict[i][0];

	bool metStartBracket = false;
	for (int i = 0, j = 0; i < srcSize && j < MAX_RES_SIZE - 1; i++, j++) {
		/* Space before character */

		if ((i - 1 > 0 && mustAddSpaceBefore(src[i]) && src[i - 1] != ' ') ||
			(src[i] == '"' && !metStartBracket))
			res[j++] = ' ';

		/* Dictionary replace */

		bool dictCorrect = false;

		for (int di = 0; di < dictSize; di++) {
			if (src[i] != firstLetDict[di])
				continue;

			if (dictItemInStr(srcSize, src, dict[di], i)) {
				bool writeInRes = false;

				for (int d = 0; d < MAX_DICT_ITEM_SIZE && dict[di][d] != '\0'; d++) {
					if (dict[di][d] == '-')
						writeInRes = true;
					else if (!writeInRes)
						i++;
					else
						res[j++] = dict[di][d];
				}
				i--; j--;
				break;
			}
		}

		/* Normal assign */

		if (!dictCorrect)
			res[j] = src[i];

		/* Dot at end of sentence */

		if (src[i] != '.' && (i + 1 == srcSize || (i + 1 < srcSize && src[i + 1] == '\n'))) {
			if (src[i] == '"') {
				res[j] = '.';
				res[++j] = '"';
			}
			else res[++j] = '.';
		}

		/* Space after character */

		if ((i + 1 < srcSize && mustAddSpaceAfter(src[i]) && src[i + 1] != ' ') ||
			(src[i] == '"' && metStartBracket))
			res[++j] = ' ';

		/* Next iter init */

		if (src[i] == '"')
			metStartBracket = !metStartBracket;

		res[j + 1] = '\0';
	}
}

void ex0() {
	char str[] = "Lok:1+1=2.\n(\"test\"text",
		 dict[MAX_DICT_SIZE][MAX_DICT_ITEM_SIZE] = { 
			 "Lok-Look", "tooo-to"
		 },
		 res[MAX_RES_SIZE];

	autoCorrect(strlen(str), str, 1, dict, res);

	std::cout << res << std::endl;
}

/*
 * Exercise 1
 */

void simulateKeyInput1(int **M, int sizeN, int sizeM) {
	int values[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };

	for (int i = 0; i < sizeN; i++) {
		for (int j = 0; j < sizeM; j++)
			M[i][j] = values[i * sizeM + j];
	}
}

void simulateKeyInput2(int **M, int sizeN, int sizeM) {
	int values[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

	for (int i = 0; i < sizeN; i++) {
		for (int j = 0; j < sizeM; j++)
			M[i][j] = values[i * sizeM + j];
	}
}

void newMatrix(int ***M, int sizeN, int sizeM) {
	*M = new int*[sizeN];
	for (int i = 0; i < sizeN; i++)
		(*M)[i] = new int[sizeM];
}

void deleteMatrix(int **M, int sizeN) {
	for (int i = 0; i < sizeN; i++)
		delete[] M[i];
	delete[] M;
}

void transformMatrix(int ***A, int N1, int M1, int **B, int N2, int M2) {
	if (N1 > N2 || M1 > M2) {
		int **temp,
			Nt = (N1 > N2) ? N2 : N1,
			Mt = (M1 > M2) ? M2 : M1;
		newMatrix(&temp, Nt, Mt);

		for (int i = 0; i < Nt; i++) {
			for (int j = 0; j < Mt; j++)
				temp[i][j] = (*A)[i][j];
		}
		deleteMatrix(*A, N1);
		*A = temp;
		N1 = Nt; M1 = Mt;
	}

	for (int i = 0; i < N1; i++) {
		for (int j = 0; j < M1; j++) {
			if ((*A)[i][j] < B[i][j])
				(*A)[i][j] = B[i][j];
			else if ((*A)[i][j] > B[i][j])
				(*A)[i][j] *= -1;
		}
	}
}

void ex1() {
	int N1 = 4, M1 = 4, N2 = 3, M2 = 3;

	int **A, **B;
	newMatrix(&A, N1, M1);
	newMatrix(&B, N2, M2);

	simulateKeyInput1(A, N1, M1);
	simulateKeyInput2(B, N2, M2);

	transformMatrix(&A, N1, M1, B, N2, M2);

	if (N1 > N2) N1 = N2;
	if (M1 > M2) M1 = M2;

	for (int i = 0; i < N1; i++) {
		for (int j = 0; j < M1; j++)
			std::cout << A[i][j] << " ";
		std::cout << std::endl;
	}

	deleteMatrix(A, N1);
	deleteMatrix(B, N2);
}

/*
 * Exercise 2''
 */

const int MAX_STR = 256;

void substr(const char *src, char *dstLeft, char *dstRight, int skipStart, int skipEnd) {
	int len = strlen(src);
	for (int i = 0, j = 0, k = 0; i < len; i++) {
		if (i < skipStart) {
			dstLeft[j++] = src[i];
			dstLeft[j] = '\0';
		}
		else if (i > skipEnd) {
			dstRight[k++] = src[i];
			dstRight[k] = '\0';
		}
	}
}

bool isWord(char *str);

bool checkForD(char *str, int ind) {
	char tmpLeft[MAX_STR] = { '\0' }, tmpRight[MAX_STR] = { '\0' }, tmpLeftover[MAX_STR] = { '\0' };

	substr(str, tmpLeft, tmpRight, ind, ind);

	// TODO: Fix cases like CAABDAAB (this should be true)
	int lenL = strlen(tmpLeft), lenR = strlen(tmpRight);
	if (lenL != lenR && lenL > 0 && lenR > 0) {
		char tmptmp[MAX_STR];
		if (lenL > lenR) {
			substr(tmpLeft, tmpLeftover, tmptmp, lenL - lenR - 1, lenL - lenR - 1);

		}
	}

	if (strcmp(tmpLeft, tmpRight) == 0)
		return isWord(tmpLeft);
	return false;
}

bool checkForC(char *str, int ind) {
	char tmpLeft[MAX_STR] = { '\0' }, tmpRight[MAX_STR] = { '\0' };

	substr(str, tmpLeft, tmpRight, ind, ind);

	return isWord(tmpLeft) && isWord(tmpRight);
}

bool checkForAAB(char *str, int ind) {
	char tmpLeft[MAX_STR] = { '\0' }, tmpRight[MAX_STR] = { '\0' };

	substr(str, tmpLeft, tmpRight, ind, ind + 2);

	return isWord(tmpLeft) && isWord(tmpRight);
}

bool isWord(char *str) {
	int len = strlen(str);
	if (len == 0)
		return true;
	else if (len > 64)
		return false;

	std::cout << str << std::endl;

	bool result = false; int encounter = 0;

	for (int i = 0; i < len; i++) {
		if (str[i] == 'D') {
			encounter++;
			result |= checkForD(str, i);
		}
	}

	if (encounter) return result;

	encounter = 0;
	for (int i = 0; i < len; i++) {
		if (str[i] == 'C') {
			encounter++;
			result |= checkForC(str, i);
		}
	}

	if (encounter) return result;

	for (int i = 0; i < len; i++) {
		if ((i < len - 2) && (str[i] == 'A') && (str[i + 1] == 'A') && (str[i + 2] == 'B'))
			result |= checkForAAB(str, i);
	}

	return result;
}

void ex2() {
	int n;
	std::cin >> n;

	if (n < 1 || n > 1024) {
		std::cout << "Invalid n!" << std::endl;
		return;
	}

	std::cin.ignore();

	char str[MAX_STR];
	for (int i = 0; i < n; i++) {
		std::cin.getline(str, MAX_STR);
		std::cout << isWord(str) << std::endl;
	}
}

int main() {
	ex2();
}