Description
Jeremy is not known for his organizational skills, but he is now determined to change. Jeremy's plan is to place notes around the house to remind him of tasks to be done and of the proper ways to do them. Jeremy's plan also includes encrypting the messages so that his parents (who don't understand anything!) do not nag him, but in a simple way so that he can recover the original message easily.
Jeremy's encryption scheme consists of two steps:
- Enter the message, of M characters, which includes the spaces between words, into a spiral that curls inwards in a clockwise direction, starting at the top-left corner of a square. The width and height of the square enclosing the spiral are chosen to be equal to the square root of P , where P is the smallest perfect square larger than or equal to M . If M is strictly less than P , then the remaining locations in the square are filled with the character `$'.
- Write the encrypted note by writing the characters one row at a time starting with the top row.
As an example, for the following message of 33 characters
abcd fgh jklmn pqrstu wxyz1 34567
Jeremy writes the following note:
abcd ftu wxgs67$yhr5$$z q43 1jp nmlk
based on entering his original message in a square of 6 rows and 6 columns as follows:
| a | b | c | d | f | |
| t | u | w | x | g | |
| s | 6 | 7 | $ | y | h |
| r | 5 | $ | $ | z | |
| q | 4 | 3 | 1 | j | |
| p | n | m | l | k |
Your task is to write a program to encrypt Jeremy's messages with the hope that he will acquire some organizational skills, in peace. In case you have forgotten, let me remind you that a number X is a perfect square if there exists a positive integer K , such that K2 equals X . For example, 16 is a perfect square but 18 is not a perfect square.
Input
Input to this problem starts with an integer N that represents the number of messages, N > 0 , on a separate line followed by a sequence of N messages. Each message consists of M characters, 1000 ≥ M > 0 , on a single line with no blank spaces at the end.
Output
For each message, the output consists of one line that contains the note with an encrypted message.