E. Произведение строк
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рома и Денис отправились на соревнование по программированию. В долгой дороге ребята заскучали, поэтому решили придумать что-нибудь интересное. Рома придумал рецепт вкусной пиццы, а Денис придумал операцию умножения строк. По версии Дениса, произведением строки $$$s$$$ длины $$$m$$$ и строки $$$t$$$ называется строка $$$t + s_1 + t + s_2 + \ldots + t + s_m + t$$$, где $$$s_i$$$ обозначает $$$i$$$-й символ строки $$$s$$$, а знаком «+» обозначена конкатенация строк. Например, произведением строк «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$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — количество строк, которые написал Денис.

Следующие $$$n$$$ строк содержат непустые строки $$$p_1, p_2, \ldots, p_n$$$, состоящие из маленьких букв английского алфавита.

Гарантируется, что суммарная длина строк $$$p_i$$$ не превосходит $$$100\,000$$$, а также, что красота итогового произведения не превосходит $$$10^9$$$.

Выходные данные

Выведите одно целое число — красоту произведения строк.

Примеры
Входные данные
3
a
b
a
Выходные данные
3
Входные данные
2
bnn
a
Выходные данные
1
Примечание

В первом примере произведение строк равно «abaaaba».

Во втором примере произведение строк равно «abanana».