给定一个包含 $n$ 个顶点的完全无向图和 $n$ 个字符串 $s_1, s_2, \dots, s_n$，连接顶点 $i$ 和 $j$ 的边的权重等于 $s_i$ 和 $s_j$ 之间的最长公共子串（LCS）的长度。计算该图上任意生成树的最大总权重。

字符串的子串可以通过从字符串的开头和/或结尾删除一些（可能为零）字符来获得。例如，“maca”、“aca”和“cau”都是“macau”的子串，而“acu”则不是。

输入格式

每个测试文件中只有一个测试用例。 第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^6$)，表示顶点和字符串的数量。 接下来的 $n$ 行中，第 $i$ 行包含一个字符串 $s_i$ ($1 \le |s_i| \le 2 \times 10^6$)，仅由小写英文字母组成。 保证所有字符串的长度之和不超过 $2 \times 10^6$。

输出格式

输出一行，包含一个整数，表示答案。

样例

样例输入 1

4
icpc
macau
regional
contest

样例输出 1

4

样例输入 2

3
ababa
babab
aba

样例输出 2

7