Problem Description

You are given $n$ binary strings. Each time, you may remove one character from the beginning of some string and append it to the end of a new string $S$. Maximize the number of adjacent pairs of equal characters in $S$.

Input Format

The first line contains a positive integer $n$, representing the number of strings.

The next $n$ lines each contain a binary string.

Output Format

Output one integer in a single line, representing the answer.

3
0011
0110
1100

9

Hint

Sample Explanation

In an optimal strategy, the indices of the chosen strings at each step are $1,1,2,1,2,3,1,2,3,2,3,3$, and the final $S=000111111000$.

Constraints

This problem uses bundled testdata.

Let $s$ be the sum of lengths of the input binary strings.

For all testdata, it is guaranteed that $1\le n\le s\le 10^6$.

Translated by ChatGPT 5