Description

给定 $n$ 个 01 串，每次你可以从某个串开头移除一个字符并把剩下的字符串加入一个新串 $S$ 的末尾。最大化 $S$ 中相邻两个字符相同的对数。

例如你有 1010 111 两个串，如果你移除第一个串的第一个字符，则 010 被加入到 $S$ 中。

串可以重复使用。

Input Format

第一行一个正整数 $n$ 表示串的个数。

接下来 $n$ 行，每行一个 01 字符串。

Output Format

一行一个整数表示答案。

1
1100

4

5
10010
10000
01110
111111
000000

48 

Hint

【样例解释】

依次取走第一个字符，$S$ 的变化过程为 100->10000->100000，答案为 $4$。

【数据范围】

记 $|s|$ 为字符串 $s$ 的长度，$s_i$ 为第 $i$ 个字符串 。
本题采用捆绑测试。

• Subtask 1（30 pts）：$n,\sum|s_i|\le 11$；
• Subtask 2（30 pts）：$n,\sum|s_i|\le 10^3$；
• Subtask 3（30 pts）：$n,\sum|s_i|\le 10^5$；
• Subtask 4（10 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 10^6$，$n\le \sum |s_i|\le 10^6$，$\forall i\in [1,n]$，$|s_i|\ge 1$。