You’ve intercepted a series of transmissions encrypted using an interesting and stupid method, which you have managed to decipher. The messages contain only spaces and lowercase English characters, and are encrypted as follows: for all words in a sentence, the **i**th word (1-based) **word** is replaced with the word generated by applying the following recursive operation **f**(**word**, **i**):

If the length ofwordis less than or equal toi, returnword. Otherwise, return f(right half ofword,i) + f(left half ofword,i).

If **word** is of odd length, it is split such that the right side is longer. You’ve decided to have a little fun with whoever is sending the messages, and to broadcast your own messages encrypted in the same style that they are using.

## Input

Your input will begin with an integer **N**, followed by a newline and then **N** test cases. Each case consists of an unencrypted sentence containing only spaces and lowercase letters, and cases are newline-separated. There will be no leading or trailing spaces in a sentence and there will be at most 1 space character between any otherwise-adjacent characters

## Output

Output, for each case and separated by newlines, the contents of the encrypted sentence after applying the encoding method describe above to it. You may ignore traditional capitalization rules and stick to all lowercase letters.

## Constraints

5 ≤ **N** ≤ 25

Sentences will contain no more than 100 characters.

———————————

#define _CRT_SECURE_NO_WARNINGS

#include <map>

#include <set>

#include <cmath>

#include <queue>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cassert>

#include <numeric>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cfloat>

#include <ctime>

#include <climits>

using namespace std;

typedef long long int64;

typedef unsigned long long uint64;

template<typename T> int size(const T& c) { return int(c.size()); }

template<typename T> T abs(T x) { return x < 0 ? -x : x; }

template<typename T> T sqr(T x) { return x*x; }

template<typename T> bool remin(T& x, const T& y) { if (x <= y) return false; x = y; return true; }

template<typename T> bool remax(T& x, const T& y) { if (x >= y) return false; x = y; return true; }

#define FOR(i, a, b) for (int i(a), _b(b); i <= _b; ++i)

#define FORD(i, a, b) for (int i(a), _b(b); i >= _b; –i)

#define REP(i, n) for (int i(0), _n(n); i < _n; ++i)

#define REPD(i, n) for (int i((n) – 1); i >= 0; –i)

string apply(string s, int i) {

if (size(s) <= i) return s;

int k = size(s)/2;

return apply(s.substr(k), i)+apply(s.substr(0, k), i);

}

int main() {

freopen(“input.txt”, “rt”, stdin);

freopen(“output.txt”, “wt”, stdout);

int t;

scanf(“%d “, &t);

while (t –> 0) {

static char buf[1<<20];

gets(buf);

string s(buf);

istringstream iss(s);

string x;

int i = 1;

while (iss >> x) {

if (i > 1) printf(” “);

printf(“%s”, apply(x, i++).c_str());

}

printf(“\n”);

}

}