Given an encrypted message, Erwin encodes it the following way:
Removes the median letter of the word from the original word and appends it to the end of the encrypted word and repeats the process until there are no letters left.
A median letter in a word is the letter present in the middle of the word and if the word length is even, the median letter is the left one out of the two middle letters.
Given an encoded string, write a program to decode it.
Input Format:
The first line of input contains T, the number of test cases.
Each test case contains a String S, denoting the encoded word.
Output Format:
Print the decoded word for each test case in a separate line.
Constraints
\(1 \le T \le 100 \)
\(1 \le |S| \le 100000 \)
In the first test case, Erwin encoded the String "erwin". At first, he wrote down the letter 'w' after which the string became "erin", he then wrote down 'r' and the remaining string was "ein", he then wrote 'i' and the string became "en" and so on he wrote down 'e' and 'n' to get the encoded string as "wrien".
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor