题目背景

小 C 喜欢最长公共前缀，小 L 喜欢最长公共后缀。

题目描述

给定 \(n\) 个仅由小写英文字母构成的字符串，第 \(i\) 个字符串记为 \(S_i\) 。

若干个字符串的匹配度定义为：他们的最长公共前缀与最长公共后缀的长度的较小值的平方。特别地，单独一个字符串的匹配度为 \(0\) 。

你需要将所有字符串分为若干组，最大化每组字符串的匹配度之和。

输入格式

第一行一个正整数 \(n\) 。

接下来 \(n\) 行，第 \(i\) 行为一个字符串 \(S_i\) 。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

3
noipnoip
noipnoip
noipnoip

样例输出 #1

64

样例 #2

样例输入 #2

6
hello
world
problem
hehello
word
poem

样例输出 #2

6

提示

样例解释 1

一种最优方案是：

• 将全部 \(3\) 个字符串分为一组，匹配度为 \(8^2 = 64\) 。

于是输出 \(64\) 。

数据范围与约定

对于 \(16 \%\) 的测试数据，有 \(2 \leq n \leq 16\)，单个字符串长度不超过 \(10\) 。

对于另外 \(24 \%\) 的测试数据，本质不同字符串的数量不超过 \(16\) 。

有 \(28 \%\) 的测试数据中，所有字符串都是回文串。

对于 \(100 \%\) 的测试数据，有 \(2 \leq n \leq 10^5\)，所有字符串长度之和不超过 \(2 \cdot 10^5\) 。

保证输入字符串仅包含小写英文字母。