题目背景

题目描述

update：重新构造了两组数据，数据已加强

辉夜原本是生活在月宫的月之公主

辉夜在淸理永远亭的仓库时，发现了一个古老的符卡序列 $S$，可能是很久很久以前的辉夜仍生活在月宫时创造的，但现在的她已经回忆不起来了。

于是辉夜便决定对这个符卡序列进行研究，$S$ 中的符卡从0开始标号，并且辉夜创造它时使用的卡组大小不超过26,因此符卡被表示成了字母 $a$ 到字母 $z$。

辉夜对从左往右读和从右往左读都一样的序列很感兴趣，对于$S$的某个满足上述条件连续子序列$a$,其价值为$a$在$S$中的所有出现位罝中点（即若a出现在$l...r$，那么中点为$\lfloor \frac{l+r}{2} \rfloor$）的异或值。

辉夜想知道对于所有满足条件的$a$，最大的价值是多少

输入格式

第一行一个整数$num$($≤5$)，表示数据组数

每组数据占一行，有一个仅有小写字母的字符串$S$，表示符卡序列

输出格式

对于每组数据，输出一行，表示辉夜想知道的答案

1
aabacabaaa

15

提示

$1≤|S|≤10^6$