Sasha 喜欢字符串和字符串理论相关的问题。他尤其热爱后缀结构。由于 Sasha 热爱 TopForces 社区，他打算写一篇名为“关于后缀树，第 37 部分”的文章。当然，他希望每个人都能理解文章的内容，因此他决定用一些好的例子来装饰它。在 TopForces 最近举行的一场比赛后，Sasha 获得了“国际潮人（International swagger）”的称号，现在他想匹配这个称号。为了实现这一点，Sasha 想要从给定的集合中选出最“潮”的字符串。

当然，Sasha 的字符串“潮度（swagness）”概念是基于后缀结构的。准确地说，是基于后缀树。为了计算一个字符串的潮度，Sasha 执行以下操作：

1. 他构建该字符串的压缩后缀树。 回想一下，后缀树是由字符串的所有后缀构建的 trie。压缩后缀树是相同的 trie，其中连续的边被合并。参见说明部分获取示例。
2. 在压缩后缀树的每条边上，他计算写在该边上的字符串所包含的不同的非空子串的数量。

字符串的潮度定义为所有边上计算出的值的总和。不幸的是，Sasha 在后缀树方面的造诣并不像他想让你认为的那样高，他无法独自解决这个问题。帮帮他！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。 接下来的 $n$ 行，每行包含一个字符串。第 $i$ 行包含一个非空字符串 $s_i$。每个字符串完全由小写拉丁字母组成。所有字符串 $s_i$ 的总长度不超过 $5 \cdot 10^5$。

输出格式

输出 $n$ 个整数，每行一个。第 $i$ 个数字必须是字符串 $s_i$ 的潮度。

样例

输入 1

3
umqra
umnik
merkurev

输出 1

35
35
101

输入 2

1
abaaa

输出 2

17

说明

字符串 abaaa 的压缩后缀树：

边为 a，aa，baaa 和 baaa。它们分别有 1、2、7 和 7 个不同的非空子串。因此，答案为 $1 + 2 + 7 + 7 = 17$。