CF1131E.String Multiplication

Roman and Denis are on the trip to the programming competition. Since the trip was long, they soon got bored, and hence decided to came up with something. Roman invented a pizza's recipe, while Denis invented a string multiplication. According to Denis, the result of multiplication (product) of strings $s$ of length $m$ and $t$ is a string $t + s_1 + t + s_2 + \ldots + t + s_m + t$, where $s_i$ denotes the $i$-th symbol of the string $s$, and "+" denotes string concatenation. For example, the product of strings "abc" and "de" is a string "deadebdecde", while the product of the strings "ab" and "z" is a string "zazbz". Note, that unlike the numbers multiplication, the product of strings $s$ and $t$ is not necessarily equal to product of $t$ and $s$.

Roman was jealous of Denis, since he invented such a cool operation, and hence decided to invent something string-related too. Since Roman is beauty-lover, he decided to define the beauty of the string as the length of the longest substring, consisting of only one letter. For example, the beauty of the string "xayyaaabca" is equal to $3$, since there is a substring "aaa", while the beauty of the string "qwerqwer" is equal to $1$, since all neighboring symbols in it are different.

In order to entertain Roman, Denis wrote down $n$ strings $p_1, p_2, p_3, \ldots, p_n$ on the paper and asked him to calculate the beauty of the string $( \ldots (((p_1 \cdot p_2) \cdot p_3) \cdot \ldots ) \cdot p_n$, where $s \cdot t$ denotes a multiplication of strings $s$ and $t$. Roman hasn't fully realized how Denis's multiplication works, so he asked you for a help. Denis knows, that Roman is very impressionable, he guarantees, that the beauty of the resulting string is at most $10^9$.

罗曼和德尼斯正在前往编程竞赛的旅途中。由于旅途漫长，他们很快感到无聊，于是决定想点有趣的事情来做。罗曼发明了一种披萨食谱，而德尼斯则发明了一种字符串乘法。根据德尼斯的定义，长度为 $m$ 的字符串 $s$ 与字符串 $t$ 的乘积（即结果）是一个字符串：

$$t + s_1 + t + s_2 + \ldots + t + s_m + t,$$

其中 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符，“+” 表示字符串拼接。例如，字符串 "abc" 与 "de" 的乘积是字符串 "deadebdecde"，而字符串 "ab" 与 "z" 的乘积是字符串 "zazbz"。注意，与数字乘法不同，字符串 $s$ 与 $t$ 的乘积不一定等于 $t$ 与 $s$ 的乘积。

罗曼嫉妒德尼斯发明了如此酷炫的运算，于是也决定发明一个与字符串相关的东西。由于罗曼是个追求美感的人，他将一个字符串的美感定义为仅由同一字母组成的最长子串的长度。例如，字符串 "xayyaaabca" 的美感为 $3$，因为其中存在子串 "aaa"；而字符串 "qwerqwer" 的美感为 $1$，因为其中所有相邻字符均不相同。

为了逗罗曼开心，德尼斯在纸上写下了 $n$ 个字符串 $p_1, p_2, p_3, \ldots, p_n$，并请他计算字符串

$$(\ldots (((p_1 \cdot p_2) \cdot p_3) \cdot \ldots ) \cdot p_n$$

的美感，其中 $s \cdot t$ 表示字符串 $s$ 与 $t$ 的乘法。罗曼尚未完全理解德尼斯的字符串乘法是如何运作的，因此向你求助。德尼斯保证，最终字符串的美感至多为 $10^9$。

The first line contains a single integer $n$ ($2 \leq n \leq 100\,000$) — the number of strings, wroted by Denis.

Next $n$ lines contain non-empty strings $p_1, p_2, \ldots, p_n$, consisting of lowercase english letters.

It's guaranteed, that the total length of the strings $p_i$ is at most $100\,000$, and that's the beauty of the resulting product is at most $10^9$.

第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$）—— Denis 写下的字符串个数。

接下来的 $n$ 行每行包含一个非空字符串 $p_1, p_2, \ldots, p_n$，均由小写英文字母组成。

保证所有字符串 $p_i$ 的总长度不超过 $100\,000$，且最终乘积的“优美度”至多为 $10^9$。

Print exactly one integer — the beauty of the product of the strings.

输出一个整数——字符串乘积的“优美度”。

In the first example, the product of strings is equal to "abaaaba".

In the second example, the product of strings is equal to "abanana".

在第一个例子中，字符串的乘积等于 "abaaaba"。

在第二个例子中，字符串的乘积等于 "abanana"。