시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 267 207 188 79.325%

문제

선영이는 남자친구를 위해 연애 편지를 썼다. 선영이는 편지가 남들에게 읽히는 것을 막기 위해서 편지를 암호화하려고 한다.

먼저, 편지의 내용을 정사각형에 작성한다. 그 다음, 시계방향으로 90도 회전시킨다. 그 다음, 첫 행부터 마지막 행까지 순서대로 다시 편지를 작성한다. 선영이는 싸이월드 세대이기 때문에, 편지에 띄어쓰기를 쓰지 않는다.

에를 들어, 편지의 내용이 "RosesAreRedVioletsAreBlue"인 경우에, 암호화한 편지는 "eedARBtVrolsiesuAoReerles" 이 된다.

선영이가 암호화한 편지가 주어졌을 때, 원래 내용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 최대 100개이다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 암호화된 편지가 주어진다. 편지는 알파벳 소문자와 대문자로만 이루어져 있으며, 길이는 1보다 크거나 같고, 10,000보다 작거나 같으며, 항상 제곱수이다.

출력

각 테스트 케이스마다 원래 메시지를 출력한다.

예제 입력 1

3
RSTEEOTCP
eedARBtVrolsiesuAoReerles
EarSvyeqeBsuneMa

예제 출력 1

TOPSECRET
RosesAreRedVioletsAreBlue
SquaresMayBeEven
W3sicHJvYmxlbV9pZCI6IjU0MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDRcdWJjMDAgXHVkM2I4XHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViMGE4XHVjNzkwXHVjZTVjXHVhZDZjXHViOTdjIFx1YzcwNFx1ZDU3NCBcdWM1ZjBcdWM1NjAgXHVkM2I4XHVjOWMwXHViOTdjIFx1YzM3Y1x1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDNiOFx1YzljMFx1YWMwMCBcdWIwYThcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjNzdkXHVkNzg4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDNiOFx1YzljMFx1Yjk3YyBcdWM1NTRcdWQ2MzhcdWQ2NTRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIFx1ZDNiOFx1YzljMFx1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NDQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwIFx1Yzc5MVx1YzEzMVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIDkwXHViM2M0IFx1ZDY4Y1x1YzgwNFx1YzJkY1x1ZDBhOFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHVjY2FiIFx1ZDU4OVx1YmQ4MFx1ZDEzMCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNTg5XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWIyZTRcdWMyZGMgXHVkM2I4XHVjOWMwXHViOTdjIFx1Yzc5MVx1YzEzMVx1ZDU1Y1x1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzJmOFx1Yzc3NFx1YzZkNFx1YjRkYyBcdWMxMzhcdWIzMDBcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQzYjhcdWM5YzBcdWM1ZDAgXHViNzQ0XHVjNWI0XHVjNGYwXHVhZTMwXHViOTdjIFx1YzRmMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVkMFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDNiOFx1YzljMFx1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NzQgJnF1b3Q7Um9zZXNBcmVSZWRWaW9sZXRzQXJlQmx1ZSZxdW90O1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAsIFx1YzU1NFx1ZDYzOFx1ZDY1NFx1ZDU1YyBcdWQzYjhcdWM5YzBcdWIyOTQgJnF1b3Q7ZWVkQVJCdFZyb2xzaWVzdUFvUmVlcmxlcyZxdW90OyBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2VuY29kZS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTdweDsgd2lkdGg6MzI0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YzU1NFx1ZDYzOFx1ZDY1NFx1ZDU1YyBcdWQzYjhcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNmQwXHViNzk4IFx1YjBiNFx1YzZhOVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzU1NFx1ZDYzOFx1ZDY1NFx1YjQxYyBcdWQzYjhcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQzYjhcdWM5YzBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YzY0MCBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3M2NcdWJhNzAsIFx1ZDU2ZFx1YzBjMSBcdWM4MWNcdWFjZjFcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNmQwXHViNzk4IFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTQyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVuY29kZWQgTWVzc2FnZSIsImRlc2NyaXB0aW9uIjoiPHA+QWxleCB3YW50cyB0byBzZW5kIGEgbG92ZSBwb2VtIHRvIGhpcyBnaXJsZnJpZW5kIEJyaWRnZXQuIFVuZm9ydHVuYXRlbHksIHNoZSBoYXMgYSBub3N5IGZyaWVuZCwgRWxsZW4sIHdobyBtaWdodCBpbnRlcmNlcHQgaGlzIG1lc3NhZ2UgYW5kIGludmFkZSB0aGVpciBwcml2YWN5LjxcL3A+XHJcblxyXG48cD5UbyBwcmV2ZW50IHRoaXMsIEFsZXggaGFzIGludmVudGVkIGEgc2NoZW1lIHRvIG1ha2UgaGlzIG1pc3NpdmVzIGluZGVjaXBoZXJhYmxlIHRvIEVsbGVuLiBIZSBhcnJhbmdlcyB0aGUgbGV0dGVycyBpbnRvIGEgc3F1YXJlLCB3aGljaCBpcyByb3RhdGVkIGEgcXVhcnRlci10dXJuIGNsb2Nrd2lzZSwgYW5kIHRoZW4gaGUgcHV0cyB0aGUgcmVzdWx0aW5nIGxldHRlcnMgb24gYSBzaW5nbGUgbGluZSBhZ2Fpbi4gKEZvciBzaW1wbGljaXR5JnJzcXVvO3Mgc2FrZSwgQWxleCBkb2VzbiZyc3F1bzt0IHVzZSB3aGl0ZXNwYWNlIG9yIHB1bmN0dWF0aW9uIGluIGhpcyBwb2Vtcy4pPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgdGV4dCAmbGRxdW87Um9zZXNBcmVSZWRWaW9sZXRzQXJlQmx1ZSZyZHF1bzsgd291bGQgYmUgZW5jb2RlZCBhcyAmbGRxdW87ZWVkQVJCdFZyb2xzaWVzdUFvUmVlcmxlcyZyZHF1bzsgdXNpbmcgdGhlIGZvbGxvd2luZyBpbnRlcm1lZGlhdGUgc3RlcHM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZW5jb2RlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExN3B4OyB3aWR0aDozMjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5FbGxlbiBoYXMgaW50ZXJjZXB0ZWQgc29tZSBvZiBBbGV4JnJzcXVvO3MgbWVzc2FnZXMgYnV0IHRoZXkgbWFrZSBubyBzZW5zZSB0byBoZXIuIENhbiB5b3Ugd3JpdGUgYSBwcm9ncmFtIHRvIGhlbHAgaGVyIGRlY29kZSB0aGVtPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGVuY29kZWQgbWVzc2FnZTogYSBzdHJpbmcgY29uc2lzdGluZyBvZiB1cHBlci1jYXNlIGFuZCBsb3dlci1jYXNlIGxldHRlcnMgb25seS4gVGhlIGxlbmd0aCBvZiB0aGUgbWVzc2FnZSBpcyBhIHNxdWFyZSBiZXR3ZWVuIDEgYW5kIDEwIDAwMCBjaGFyYWN0ZXJzLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHRoZSBvcmlnaW5hbCBtZXNzYWdlLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d