Hide

Problem G
Encoded Message

Alex wants to send a love poem to his girlfriend Bridget. Unfortunately, she has a nosy friend, Ellen, who might intercept his message and invade their privacy.

To prevent this, Alex has invented a scheme to make his missives indecipherable to Ellen. He arranges the letters into a square, which is rotated a quarter-turn clockwise, and then he puts the resulting letters on a single line again. (For simplicity’s sake, Alex doesn’t use whitespace or punctuation in his poems.)

For example, the text “RosesAreRedVioletsAreBlue” would be encoded as
eedARBtVrolsiesuAoReerles” using the following intermediate steps:

R

o

s

e

s

A

r

e

R

e

d

V

i

o

l

e

t

s

A

r

e

B

l

u

e

$\Rightarrow $

e

e

d

A

R

B

t

V

r

o

l

s

i

e

s

u

A

o

R

e

e

r

l

e

s

Ellen has intercepted some of Alex’s messages but they make no sense to her. Can you write a program to help her decode them?

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with an encoded message: a string consisting of upper-case and lower-case letters only. The length of the message is a square between 1 and 10 000 characters.

Output

Per test case:

  • one line with the original message.

Sample Input 1 Sample Output 1
3
RSTEEOTCP
eedARBtVrolsiesuAoReerles
EarSvyeqeBsuneMa
TOPSECRET
RosesAreRedVioletsAreBlue
SquaresMayBeEven

Please log in to submit a solution to this problem

Log in