Given a complete undirected graph of vertices and strings , the weight of edge connecting vertices and is equal to the length of the longest common substring (LCS) between and . Compute the maximum total weight of any spanning tree on this graph.

A substring of a string can be obtained by removing some (possibly zero) characters from the beginning and/or the end of that string. For example, "maca", "aca" and "cau" are all substrings of "macau", while "acu" is not.

输入描述:

There is only one test case in each test file.
The first line of the input contains one integer  () indicating the number of vertices and strings.
For the following  lines, the -th line contains one string  () consisting only of lowercase English letters.
It's guaranteed that the sum of lengths of all strings will not exceed .

输出描述:

Output one line containing one integer indicating the answer.

4
icpc
macau
regional
contest

4

3
ababa
babab
aba

7