Background

This problem is collecting fake solutions and hack testdata. If you got AC with a fake solution, feel free to private message the setter with a hack.

The information may be redundant.

— command_block, "Pre-exam Tips"

djy was reading P8001, misread the problem, got very upset, and then this problem was created.

Problem Description

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

For example, if you have two strings 1010 111, and you remove the first character of the first string, then 010 is appended to $S$.

Strings can be reused.

Input Format

The first line contains a positive integer $n$, indicating 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.

1
1100

4

5
10010
10000
01110
111111
000000

48 

Hint

[Sample Explanation]

By removing the first character each time, the changes of $S$ are 100->10000->100000, and the answer is $4$.

[Constraints]

Let $|s|$ be the length of string $s$, and $s_i$ be the $i$-th string.
This problem uses bundled tests.

• 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): no additional constraints.

For $100\%$ of the data, $1\le n\le 10^6$, $n\le \sum |s_i|\le 10^6$, and for all $i\in [1,n]$, $|s_i|\ge 1$.

Translated by ChatGPT 5