lh8k 是一个喜欢拾荒的人。有一天，他发现了一台打字机。这台打字机有一个按钮和两个纸槽。经过一番实验，他弄清楚了这台打字机的工作原理。

1. 开始时，你需要将两张纸分别插入两个纸槽中，上层纸槽中的纸作为模板，下层纸槽中的纸为空白。打字机会读取上层纸槽中纸的内容并将其写入下层纸槽的纸上。为方便起见，我们将上层纸槽中纸的内容记为字符串 $T$，下层纸槽中纸的内容记为 $S$，初始时 $S = \varepsilon$（空）。
2. 打字机在上层和下层纸槽中各有一个指针。我们将上层和下层纸槽中指针的位置分别记为 $p$ 和 $q$，初始时两个指针都指向纸的开头，即 $p = q = 1$。
3. 每次按下按钮时，打字机会读取上层纸槽中指针位置处的字符，并将其写入下层纸槽中指针所指的位置（即 $S[q] := T[p]$）。打印完成后，两个纸槽中的指针都会“移动”$^*$。下层纸槽中的指针总是向前移动（$q := q + 1$）；上层纸槽中的指针初始时也向前移动，但如果当前指针位置处于 $T$ 的末尾，它将向后移动，持续移动直到到达 $T$ 的开头，然后再次向前移动，重复此循环。

例如，如果 lh8k 在上层纸槽中插入字符串 $T = \text{abcd}$ 并按下按钮 20 次，他将在下层纸槽中得到打印好的字符串 $S = \text{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$ 的最短长度，$\oplus$ 表示按位异或运算。

$^*$实际上，是纸在移动。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^3$)，表示测试用例的数量。

对于每个测试用例，有一行包含一个仅由小写英文字母组成的字符串 $S$ ($1 \le |S| \le 10^6$)，表示 lh8k 想要使用打字机打印的字符串。

数据保证 $\sum |S| \le 10^6$。

输出格式

对于每个测试用例，输出一行一个整数，表示 $\bigoplus_{i=1}^{|S|} i \times ans_i$ 的值，其中 $ans_i$ 的含义如题目描述中所述。

样例

样例输入 1

5
a
aa
ababa
abcdcbabcdcbabcdcbab
popipopi

样例输出 1

1
3
1
92
51