众所周知，Yuta 不擅长数数。Rikka 很担心这种情况，于是她给了 Yuta 一些计数任务来练习。以下是其中之一：

在计算机编程中，字符串传统上是一个字符序列，而字符串的子串是该字符串内连续的字符序列。例如，snowball 是一个字符串，now 是 snowball 的子串，而 bow 不是 snowball 的子串。此外，两个字符串 $U$ 和 $V$ 的拼接称为 $UV$，也就是说，如果 $U$ 是 snow，$V$ 是 ball，那么 $UV$ 就是 snowball。

Rikka 有一个长度为 $n$ 的字符串 $S$，她想让 Yuta 计算总共有多少个不同的“好”字符串。在这里，她称一个非空字符串 $T$ 为“好”的，如果：

• $T$ 是 $S$ 的子串；且
• 对于任何满足 $TP$ 和 $PT$ 相等的非空字符串 $P$，$TP$ 都不是 $S$ 的子串。

这对 Yuta 来说太难了。你能帮帮他吗？

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。

对于每个测试用例，唯一的一行包含一个长度为 $n$ ($1 \le n \le 2 \times 10^5$) 的字符串 $S$，仅由小写字母组成。

输入保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，即答案。

样例

样例输入 1

6
rikkasuggeststoallthecontestants
thisisaproblemdesignedforgrandmasters
ifyoudidnotachievethat
youdbetterskiptheproblem
wishyouahighrank
enjoytheexperience

样例输出 1

500
679
244
290
132
163