Maximizing Prefix Sum via Single Modification

Given n strings \(s_1, s_2, \dots, s_n\) consisting of lowercase English letters, define the total prefix score \(V\) as:

\[ V = \sum_{i<j} P(s_i, s_j), \]

where \(P(s_i, s_j)\) is the length of the longest common prefix between \(s_i\) and \(s_j\). You are allowed to choose exactly one string and modify exactly one character in that string. Determine the maximum possible value of \(V\) after this single modification.

inputFormat

The first line contains an integer \(n\) representing the number of strings. Each of the next \(n\) lines contains a non-empty string composed of lowercase English letters.

outputFormat

Output a single integer --- the maximum total prefix score after modifying exactly one character in one of the strings.

sample

3
abc
abd
bbc

7