// Hagopian==Encoded Message
 
#include <iostream>
//#include
using namespace std;

char** encrypt(char** plain, char** cypher, int msgSize);
char** decrypt(char** plain, char** cypher, int msgSize);

int main() {
	int tests{}, msgSize{};
	cin >> tests;// >> msgSize;
	//msgSize = sqrt(msgSize);
	char ch{};
	char* msg = new char[10000];
	cin.ignore(1000, '\n');
	while (tests--) {	
		while (cin.get(ch) && ch != 10) {
			msg[msgSize] = ch;
			++msgSize;
		}
		msg[msgSize] = 0;
		cout << "msg = " << msg << endl;

		msgSize = sqrt(strlen(msg));
		//allocate memory for a matrix of plain text characters
		char** matrix = new char* [msgSize];
		for (int i = 0; i < msgSize; ++i) {
			matrix[i] = new char[msgSize];
		}
		//allocate memory for a matrix of cypher text characters
		char** cypher = new char* [msgSize];
		for (int i = 0; i < msgSize; ++i) {
			cypher[i] = new char[msgSize];
		}
		//initialize matrix of plain text characters
		for (int i = 0; i < msgSize; ++i) {
			for (int j = 0; j < msgSize; ++j) {
				matrix[i][j] = msg[i * msgSize + j];
			}
		}
		cypher = encrypt(matrix, cypher, msgSize);
		cout << "The plain text in matrix form:\n";
		for (int i = 0; i < msgSize; ++i) {
			for (int j = 0; j < msgSize; ++j) {
				cout << matrix[i][j] << " ";
			}
			cout << endl;
		}
		cout << "The cypher text:\n";
		for (int i = 0; i < msgSize; ++i) {
			for (int j = 0; j < msgSize; ++j) {
				cout << cypher[i][j];
			}
			//cout << endl;
		}
		cout << "\nThe plain text recovered:\n";
		matrix = decrypt(matrix, cypher, msgSize);
		for (int i = 0; i < msgSize; ++i) {
			for (int j = 0; j < msgSize; ++j) {
				cout << matrix[i][j];
			}
			//cout << endl;
		}
		for (int i = 0; i < msgSize; ++i) {
			delete[] matrix[i];
			delete[] cypher[i];
		}
		delete[] matrix;
		delete[] cypher;
		cout << endl;
	}
}


char** encrypt(char** plain, char** cypher, int msgSize) {
	for (int i = 0; i < msgSize; ++i) {
		for (int j = 0; j < msgSize; j++) {
			cypher[i][j] = plain[j][(msgSize-1-i)];
			//*(cypher + i * msgSize + j) = *(plain + j * msgSize + msgSize - 1 - i);
		}
	}
	return cypher;
}

char** decrypt(char** plain, char** cypher, int msgSize) {
	for (int i = 0; i < msgSize; ++i) {
		for (int j = 0; j < msgSize; j++) {
			plain[i][j] = cypher[msgSize - 1 - j][i];
		}
	}
	return plain;
}