Рома и Денис отправились на соревнование по программированию. В долгой дороге ребята вспоминали операции над строками. Денис сказал, что в Python строки можно умножать на число, тогда Рома, программирующий на С++, решил придумать операцию перемножения строк. По версии Ромы, умножение строки s длины n на строку t обозначается как s·t и равно строке t+s
1+t+s
2+...+t+s
n+t, где s
i обозначает i-й символ строки s, а знаком « + » обозначено сложение (конкатенация) строк. Например, произведением строк « abc » и « de » является строка « deadebdecde », а произведением строк « z » и « ab » является строка « abzab ». Обратите внимание, что, в отличие от умножения чисел, произведение строк s и t, вообще говоря, не равно произведению строк t и s.
Денис решил продолжить мысль Ромы — он, как ценитель прекрасного, решил определить красоту строки как максимальную длину подряд идущей группы одинаковых букв. Например, красота строки « xayyaaabca » равна 3, так как самая длинная группа подряд идущих одинаковых букв — это « aaa », а красота строки « qwerqwer » равна 1, потому что все соседние буквы в ней различны.
Чтобы развлечь Дениса, Рома написал ему на листочке n строк p
1,p
2, p
3, ... ,p
n и попросил его вычислить красоту строки (...((p
1·p
2)·p
3)·...)p
n. Денис не до конца понял, как работает умножение Ромы, но не хочет признаваться в этом, поэтому просит посчитать красоту этой строки вас. Рома знает, что Денис слишком впечатлительный, поэтому гарантирует, что красота полученной строки не превосходит 10
9.
Входные данные
В первой строке содержится число n (1 ≤ n ≤ 100000) — количество строк, которые написал Рома.
В следующих n строках содержатся непустые строки p
1, p
2, ..., p
n, состоящие из маленьких букв английского алфавита.
Гарантируется, что суммарная длина строк не превосходит 100000, а также, что красота произведения всех строк не превосходит 10
9.
Выходные данные
Выведите одно целое число — красоту произведения строк.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
3
a
b
a |
3 |
произведение трёх строк равно « abaaaba » |
| 2 |
2
bnn
a |
1 |
произведение двух строк равно « abanana » |