Given a collection of N words, find an arrangement of the words that divides them among N lines, padding them with leading spaces to maximize the number of non-space characters that are the same as the character immediately above them on the preceding line. Your score for this game is that number.

Input

Input data will consist of one or more test sets.

The first line of each set will be an integer N (1 ≤ N ≤ 10) giving the number of words in the test case. The following N lines will contain the words, one word per line. Each word will be made up of the characters 'a' to 'z' and will be between 1 and 10 characters long (inclusive).

End of input will be indicated by a non-positive value for N.

Output

Your program should output a single line containing the maximum possible score for this test case, printed with no leading or trailing spaces.

Sample Input

5
abc
bcd
cde
aaa
bfcde
0

Sample Output

8

Hint

One possible arrangement yielding this score is:

aaa
abc
 bcd
  cde
bfcde