今年木叶再次举办中忍选拔考试,参加考试的有$$$n$$$忍者,名字分别为$$$s_1$$$、$$$s_2$$$、...、$$$s_n$$$。所有的名字都是不同的。考试阶段之一包括参与者之间的战斗。今年每场比赛确定忍者的规则如下:如果满足以下条件,忍者 $$$i$$$ 和 $$$j$$$ 将相互对战:
- $$$i \neq j$$$;
- $$$s_{j}$$$ 是 $$$s_{i}$$$ 的子串;
- 除了$$$i$$$和$$$j$$$之外,没有$$$k$$$,$$$s_{j}$$$是$$$s_{k}$$$的子串,而$$$s_{k}$$$是$$$s_{i}$$$的子串。
字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
你的任务是找出今年将发生多少场战斗。
输入
第一行由唯一的整数 $$$n$$$ ($$$1 \leq n \leq 10^{6}$$$) 组成,代表考生人数。
以下 $$$n$$$ 行包含它们的名称。没有两个名称重合,所有名称都非空且由小写英文字母组成。所有名称的总长度不超过$$$10^6$$$。
输出
打印代表战斗次数的唯一整数。
示例
输入 #1
5 hidan dan hanabi bi nabi
输出 #1
3
输入 #2
4 abacaba abaca acaba aca
输出 #2
4
注意
在第一个示例中,hidan 与 dan 战斗,hanabi 与 nabi 战斗,nabi 也与 bi 战斗。名为“hanabi”和“bi”的忍者不会互相战斗,因为有一个名为“nabi”的忍者为他们打破了第三个条件。
在第二个示例中,战斗在 abacaba 和 acaba、abacaba 和 abaca、acaba 和 aca、abaca 和 aca 之间进行。