Secret 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’.

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$.

For each original message, output the secret message.

Sample Input 1 | Sample Output 1 |
---|---|

2 iloveyoutooJill TheContestisOver |
iteiloylloooJuv OsoTvtnheiterseC |