题目描述

众所周知，Yuta 不擅长计数。Rikka 对此感到担忧，于是她给 Yuta 布置了一些计数任务作为练习。以下是其中之一：

在计算机编程中，字符串通常是指一个字符序列，而一个字符串的子串是指该字符串内的一个连续字符序列。例如，$\text{snowball}$ 是一个字符串，$\text{now}$ 是 $\text{snowball}$ 的一个子串，而 $\text{bow}$ 不是 $\text{snowball}$ 的子串。此外，两个字符串 $U$ 和 $V$ 的拼接记作 $U V$，也就是说，如果 $U$ 是 $\text{snow}$ 而 $V$ 是 $\text{ball}$，那么 $U V$ 就是 $\text{snowball}$。

Rikka 有一个长度为 $n$ 的字符串 $S$，她希望 Yuta 统计一共有多少个不同的 好的 字符串。这里，她称一个非空字符串 $T$ 为 好的，当且仅当

• $T$ 是 $S$ 的一个子串；并且
• 对于任何满足 $T P$ 与 $P T$ 是同一字符串的非空字符串 $P$，$T P$ 都不是 $S$ 的子串。

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

输入格式

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试数据的组数。

对于每组测试数据，仅有一行包含一个仅由小写字母组成的字符串 $S$，其长度为 $n$（$1 \le n \le 2 \times 10^5$）。

输入保证所有测试数据的 $n$ 之和不超过 $5 \times 10^6$。

输出格式

对于每组测试数据，输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

6
rikkasuggeststoallthecontestants
thisisaproblemdesignedforgrandmasters
ifyoudidnotachievethat
youdbetterskiptheproblem
wishyouahighrank
enjoytheexperience

输出 #1

500
679
244
290
132
163