既然你已经向HC提出了一个假帖子2 Facebook 页面,Heidi 希望在实际发布帖子之前衡量帖子的质量。她最近看到一篇(可能是假的)关于分形结构对多媒体消息的影响的文章,她现在正在尝试测量消息的自相似性,其定义为

其中总和是所有非空字符串的总和 p 和
是出现的次数 p in s 作为 子字符串。 (请注意,总和是无限的,但它只有有限数量的非零被加数。)
海蒂拒绝做任何其他事情,直到她知道如何计算这种自相似性。你能帮帮她吗? (如果你想说服海蒂,有限弦无论如何都不能是分形——不用费心,我们已经尝试过了。)
输入
输入以指示测试用例数量的行开头 T (1 ≤ T ≤ 10)。之后, T 测试用例如下,每个测试用例由一行包含一个字符串组成 s (1 ≤ |s| ≤ 100 000) 由小写字母 (a-z).
输出
输出 T 行,每一行包含一个数字——相应测试用例的答案。
示例
输入复制
4
aa
abcd
ccc
abcc
输出复制
5
10
14
12
注意
一个字符串 s 包含另一个字符串 p 作为子字符串 if p 是一个连续的子序列 s。例如, ab 是一个子串 驾驶室 但不是 acb.