#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(char *str, char *dst, int startInd, int endInd) {
	for (int i = startInd, j = 0; i <= endInd; i++)
		dst[j++] = str[i];
}

void splitStr(char *src, char *dstLeft, char *dstRight, int skipStart, int skipEnd) {
	subStr(src, dstLeft, 0, skipStart - 1);
	int len = strlen(src);
	subStr(src, dstRight, skipEnd + 1, len - 1);
}

void symSplitStr(char *src, char *dstLeft, char *dstRight, char *dstLeftover, int skipStart, int skipEnd) {
	int len = strlen(src);

	if (len - skipEnd > skipStart) {
		subStr(src, dstLeft, 0, skipStart - 1);
		subStr(src, dstRight, skipEnd + 1, skipEnd + skipStart);
		subStr(src, dstLeftover, skipEnd + skipStart + 1, len - 1);
	}
	else {
		subStr(src, dstLeftover, 0, skipStart - 1 - (len - 1 - skipEnd));
		subStr(src, dstLeft, skipStart - (len - 1 - skipEnd), skipStart - 1);
		subStr(src, dstRight, skipEnd + 1, len - 1);
	}
}

bool isWord(char *str);

int checkForD(char *str) {
	int len = strlen(str);
	int status = -1;

	for (int i = 0; i < len; i++) {
		if (str[i] == 'D') {
			if (status == -1) status = 0;

			char tmpLeft[MAX_STR] = { '\0' }, tmpRight[MAX_STR] = { '\0' }, tmpLeftover[MAX_STR] = { '\0' };
		
			int len = strlen(str);
			if (i != len - i - 1 && i > 0 && i < len - 1)
				symSplitStr(str, tmpLeft, tmpRight, tmpLeftover, i, i);
			else
				splitStr(str, tmpLeft, tmpRight, i, i);
		
			if (strcmp(tmpLeft, tmpRight) == 0)
				status |= isWord(tmpLeft) && isWord(tmpLeftover);
		}
	}

	return status;
}

int checkForC(char *str) {
	int len = strlen(str);

	for (int i = 0; i < len; i++) {
		if (str[i] == 'C') {
			char tmpLeft[MAX_STR] = { '\0' }, tmpRight[MAX_STR] = { '\0' };

			splitStr(str, tmpLeft, tmpRight, i, i);

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

int checkForAAB(char *str) {
	int len = strlen(str), indA = -1, indB = -1;
	for (int i = 0; i < len; i++) {
		if ((i < len - 1) && indA < 0 && (str[i] == 'A') && (str[i + 1] == 'A'))
			indA = ++i;
		else if (indA >= 0 && str[i] == 'B')
			indB = i;
	}

	if (indA >= 0 && indB > 0) {
		if (indA > 1 || indB < len - 1)
			return false;

		char tmpMiddle[MAX_STR] = { '\0' };

		subStr(str, tmpMiddle, indA + 1, indB - 1);

		return isWord(tmpMiddle);
	}
	return -1;
}

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

	int tmp;

	tmp = checkForD(str);
	if (tmp < 0) {
		tmp = checkForC(str);
		if (tmp < 0) {
			tmp = checkForAAB(str);
		}
	}
	if (tmp > 0) return tmp;

	tmp = checkForC(str);
	if (tmp < 0) {
		tmp = checkForD(str);
		if (tmp < 0) {
			tmp = checkForAAB(str);
		}
	}
	if (tmp > 0) return tmp;

	tmp = checkForAAB(str);
	if (tmp < 0) {
		tmp = checkForD(str);
		if (tmp < 0) {
			tmp = checkForC(str);
		}
	}
	if (tmp > 0) return tmp;

	tmp = checkForAAB(str);
	if (tmp < 0) {
		tmp = checkForC(str);
		if (tmp < 0) {
			tmp = checkForD(str);
		}
	}
	if (tmp > 0) return tmp;

	return false;
}

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