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

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