← 返回题目列表

Codeforces · 802/G3

G3. 假新闻(硬)

中文机器翻译题面 查看原题

既然你已经向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.