Max has been procrastinating on his English summative and needs help finishing it.

Since Max knows his teacher loves alliterations, he would also love when two consecutive characters are the same in a string.

Max has written ~N~ words, ~S_i~, for his summative most of which are gibberish but needs you to clean it up for him to maximize his summative mark.

A string can be derived from these ~N~ words by selecting some (or all) of them and concatenating them together without changing the order.

The score of a string is determined by the number of two-letter substrings that only use one character.

This score determines his summative mark.

Can you help Max find out his maximum summative mark?

Constraints

~1 \le N \le 2 \times 10^5~

~1 \le |S_i| \le 5~

Note that ~|S_i|~ denotes the length of the string ~S_i~.

~S_i~ will only contain lowercase letters.

Subtask 1 [20%]

~1 \le N \le 20~

Subtask 2 [40%]

~1 \le N \le 1\,000~

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line will contain an integer, ~N~, the number of words.

The next ~N~ lines will contain a word, ~S_i~, the ~i^\text{th}~ word.

Output Specification

Output the maximum score (i.e., the maximum number of two-letter substrings that only use one character from a subsequence of the ~N~ words).

Sample Input

5
ro
r
oo
yo
oort

Sample Output

4

Explanation for Sample Output

If the first, third, fourth, and fifth words are concatenated, the final string is roooyooort, and there are ~4~ substrings that two-letter substrings that have the same character: ~[2, 3], [3, 4], [6, 7], [7, 8]~. It can be proven that this is the maximum score.