题目描述Description

lh8k 是一个喜欢拾荒的人。有一天他发现了一台打字机。这台打字机上有一个按钮和两个纸槽。经过一番折腾，他发现了这个打字机的工作规律

1. 开始时，你需要向两个纸槽中塞入两张纸条，其中上纸槽中塞入一张已经有文字的纸条作为模板，下纸槽塞入一张空白纸条。打字机会从上纸槽中的纸条读取内容写到下纸槽中的纸条中。为了方便，我们记上纸槽中纸条的内容为字符串 T，下纸槽中的为 S，初始时 S=\varepsilon 为空。

2. 打字机在上下两个纸槽中均有一个指针。我们记上纸槽和下纸槽中的指针指向的位置分别为 p 和 q，初始时这两个指针都指向两个纸条开始的地方，即 p=q=1。

3. 每次按下按钮，打字机会从上纸槽的指针处读取文字，并将该文字写入到下纸槽指针所指位置。（即 S[q]:=T[p]），在打印完毕后，两个纸槽中的指针均会发生"移动"¹。下纸槽中的指针始终向前移动（q:=q+1）；上纸槽中的指针开始时也是向前移动，但是若当前指针指向的位置为 T 的末尾的话，则会反向移动，一直移动到 T 的开头后又反向，循环往复。

比方说，若 lh8k 在上纸槽中插入一个写有 T=\mathtt{abcd} 的字符串，并且按下 20 次按钮，那么他就会在下纸槽中获得一张打印有 S=\mathtt{abcdcbabcdcbabcdcbab} 字符串的纸条。此外若 |T|=1，则打印出的 S 只有一种字符，即 S 由 T[1] 重复若干次组成。

lh8k 现在想要通过这个打字机打印出一个字符串 S，他想 T 的长度越短越好。他想知道 T 的长度最短可以是多少？请注意，从打印开始到结束不能更换纸条，也不能随意更改纸条和指针位置。打印 S 时必须从 T 的开头正向开始。

不过对于上述这个问题 lh8k 觉得只求一次答案不够过瘾，因此他想对 S 的每个前缀 S' ，都求一遍最短的 T 长度是多少。

由于串总长度过长，因此对于每个串只需要输出 \bigoplus_{i=1}^{|S|} i \times ans_i 的值，其中 ans_i 表示的是长度为 i 的前缀对应的最短的 T 的长度，\bigoplus 表示按位异或。

输入格式Input

第一行一个整数 t（1\le t\le 10^3），表示测试数据组数。

对于每组数据，一行一个仅由小写英文字母组成的字符串 S（1\le |S|\le 10^6），表示 lh8k 想要通过打字机打印出的字符串。

数据保证 \sum|S|\le10^6。

输出格式Output

对于每组数据，输出一行一个整数，表示 \bigoplus_{i=1}^{|S|} i \times ans_i 的值，其中 ans_i 的含义见题面。

样例Sample

提示Hint

-

出题Author

来源Source