UNCA High School Programming Competition 2017

#### Start

2017-04-08 08:00 AKDT

## UNCA High School Programming Competition 2017

#### End

2017-04-08 12:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1699 days 18:30:53

4:00:00

0:00:00

# Problem GEncoded 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