月宫的符卡序列

题目背景

![](https://cdn.luogu.com.cn/upload/pic/60728.png)

题目描述

**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

1
aabacabaaa

输出样例 #1

15

说明

$1≤|S|≤10^6$