Cipher Key

For all the hundreds of years that states, borders, and recurring conflicts between countries have existed, so has the system of espionage. An agent living in one country, legally or illegally, sends reports containing state secrets to another country. The ways of transmitting reports change constantly. A hundred years ago they were paper letters, fifty years ago they were radiograms, and now a report can even be sent by electronic mail. One feature of every report has not changed and never will: any information message can be intercepted. To guard against this, reports are encrypted so that only the intended recipient can read them. This usually uses a key, a relatively short string, often meaningless, that makes it possible to decrypt the report. Also, so that a captured agent cannot reveal the key to interested parties, each report has its own key, which is sent along with the report, encrypted as well but by a not very complicated method. You must learn to obtain this key from its encrypted version for a certain encryption algorithm.

To encrypt a nonempty key s, the agent first chooses a string t such that s is a prefix of t and the reversed string s is a suffix of t. The string t may contain characters unrelated to s. Then some random (possibly zero) number of random characters is appended to the left of t, and exactly the same number of possibly different random characters is appended to the right. Now t is the encrypted form of the key s.

Clearly, when trying to recover the key, that is, the original string s, several candidates may arise. Therefore it was decided that the key must be the longest string among all possible candidates, and if several such strings exist, the one for which the number of random characters appended on the left and right is minimal, that is, the string t has maximum length. You must implement an algorithm that recovers the key s from its encrypted form.

The first line contains a single integer n, the number of keys you need to decrypt. The next n lines contain the encrypted forms of the sought keys, one per line. Each encrypted form consists only of lowercase Latin letters. The total length of all encrypted keys does not exceed 100000 characters. It is guaranteed that for each encrypted form there exists at least one suitable nonempty key.

Print the n decrypted keys, one per line.