Background

Problem Description

Update: Two sets of testdata have been rebuilt, and the testdata has been strengthened.

Kaguya was originally a princess of the Moon who lived in the Moon Palace.

When Kaguya was cleaning the warehouse of Eientei, she found an ancient spell card sequence $S$. It might have been created a very, very long time ago, when Kaguya still lived in the Moon Palace, but now she cannot remember it anymore.

So Kaguya decided to study this spell card sequence. The spell cards in $S$ are indexed starting from $0$. Also, when she created it, the deck size did not exceed $26$, so each spell card is represented by a letter from $a$ to $z$.

Kaguya is very interested in sequences that read the same from left to right and from right to left. For any contiguous subsequence $a$ of $S$ that satisfies the above condition, its value is defined as the XOR of the midpoints of all occurrences of $a$ in $S$ (that is, if $a$ occurs at $l...r$, then the midpoint is $\lfloor \frac{l+r}{2} \rfloor$).

Kaguya wants to know, among all such $a$, what the maximum value is.

Input Format

The first line contains an integer $num$ ($\le 5$), indicating the number of test cases.

Each test case consists of one line containing a string $S$ with only lowercase letters, representing the spell card sequence.

Output Format

For each test case, output one line representing the answer Kaguya wants to know.

1
aabacabaaa

15

Hint

$1 \le |S| \le 10^6$

Translated by ChatGPT 5