紫（Yukari）是一位难以捉摸的妖怪，她可以操纵边界。最近紫的心情很不好，当她听到有人说她不喜欢的话（例如“紫已经几千岁了”）时，她会感到愤怒并从背后袭击那个人。灵梦（Reimu）已经被她困扰了一段时间，因为她不知道哪些词会让紫不高兴。即使是说一些常见的词，比如“cooooooooooooooooooooooool”、“我想吃面条”或“无敌风火轮”，也会遭到紫的袭击。

为了避免激怒紫，灵梦找出了 $n$ 个紫可能讨厌的词，编号为 $1$ 到 $n$。每个词都是一个仅包含小写英文字母的字符串。然而，一些冗余（不必要）的词可能包含其他词。例如，如果“iwanttoeatnoodles”和“noodles”都是可能的词，那么前者就是冗余的。

灵梦想要估算这 $n$ 个词之间有多少冗余关系。形式化地，令 $s_i$ 表示第 $i$ 个词。灵梦想要知道，有多少个三元组 $(i, j, k)$（$1 \le i, j, k \le n$；$i, j, k$ 两两不同）满足以下条件：$s_i$ 是 $s_j$ 的子串，且 $s_j$ 是 $s_k$ 的子串。此外，不存在另一个 $j'$，使得 $j' \neq i, j, k$，且 $s_i$ 也是 $s_{j'}$ 的子串，同时 $s_{j'}$ 也是 $s_k$ 的子串。

灵梦请求你帮助她计算这类三元组的数量。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 10^6$)，表示词的数量。

接下来 $n$ 行。第 $i$ 行包含一个由小写字母组成的非空字符串 $s_i$，表示第 $i$ 个词。保证所有词互不相同，且满足 $\sum_{i=1}^n |s_i| \le 2 \times 10^6$。

输出格式

输出一个整数，即题目描述中所述的答案。

样例

样例输入 1

8
wwwsoupunetcom
wwwsoupunet
soupunet
punetcom
punet
pun
net
n

样例输出 1

6

样例输入 2

4
a
aa
aaa
aaaa

样例输出 2

2

样例输入 3

5
bc
cbcb
cbca
cbc
c

样例输出 3

3

说明

对于第一个样例，有效的元组为 $(3, 2, 1), (5, 3, 2), (6, 5, 3), (6, 5, 4), (7, 5, 3)$ 和 $(7, 5, 4)$。