Hide

# Problem ESecret Message

Jack and Jill developed a special encryption method, so they can enjoy conversations without worrrying about eavesdroppers. Here is how: let $L$ be the length of the original message, and $M$ be the smallest square number greater than or equal to $L$. Add $(M - L)$ asterisks to the message, giving a padded message with length $M$. Use the padded message to fill a table of size $K \times K$, where $K^2 = M$. Fill the table in row-major order (top to bottom row, left to right column in each row). Rotate the table $90$ degrees clockwise. The encrypted message comes from reading the message in row-major order from the rotated table, omitting any asterisks.

For example, given the original message ‘iloveyouJack’, the message length is $L=12$. Thus the padded message is ‘iloveyouJack****’, with length $M=16$. Below are the two tables before and after rotation.

 i l o v e y o u J a c k * * * *
 * J e i * a y l * c o o * k u v

Then we read the secret message as ‘Jeiaylcookuv’.

## Input

The first line of input is the number of original messages, $1 \le N \le 100$. The following $N$ lines each have a message to encrypt. Each message contains only characters a–z (lower and upper case), and has length $1 \le L \le 10\, 000$.

## Output

For each original message, output the secret message.

Sample Input 1 Sample Output 1
2
iloveyoutooJill
TheContestisOver

iteiloylloooJuv
OsoTvtnheiterseC

Hide