Kattis

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