题目描述

给定一个字符串 $S$，假设其前缀子串 $\text{Str}_i = S[0..i]$，字符串的长度为 $N$。例如，当 $S = \text{"moreandmorecold"}$ 且 $N = 15$ 时，有 $\text{Str}_0 = \text{"m"}$、$\text{Str}_1 = \text{"mo"}$、$\text{Str}_2 = \text{"mor"}$，以此类推。

我们定义 $c[i]$ 表示前缀子串 $\text{Str}_i$ 在字符串 $S$ 中出现的次数。现在，请你计算 $c[0]$ 到 $c[N-1]$ 的总和。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。
对于每个测试用例，仅有一行输入，包含一个仅由小写字母组成的字符串 $S$，字符串的长度小于 $100000$。

输出格式

对于每个测试用例，输出一个整数，表示 $c[0] + c[1] + \dots + c[N-1]$ 的结果。

3
acacm
moreandmorecold
thisisthisththisisthisisthisththisis

7
19
82

提示

对于第一个测试用例：
在字符串 "acacm" 中，出现了两次 "a"，两次 "ac"，以及一次 "aca"、"acac" 和 "acacm"。因此答案为 $2 + 2 + 1 + 1 + 1 = 7$。