Задача 38302. Product of strings

Roma and Denis went to a programming competition. On the long road, the guys remembered operations on strings. Denis said that in Python strings can be multiplied by a number, then Roma, a C++ programmer, decided to come up with a string multiplication operation. According to Roma, the multiplication of a string s of length n by a string t is denoted as s·t and is equal to the string t+s₁+t+s₂+...+t+ s_n+t, where s_i denotes the i-th character of the string s, and « + " addition (concatenation) of strings is indicated. For example, the product of the strings « abc " and « de» is the string " deadebdecde », but by the product of the lines « z » and « ab » is the string " abzab ". Note that, unlike multiplication of numbers, the product of the strings s and t is not, in general, the product of the strings t and s.

Denis decided to continue the thought of Roma — he, as a connoisseur of beauty, decided to define the beauty of a line as the maximum length of a consecutive group of identical letters. For example, the beauty of the line " xayyaaabca » is 3 because the longest group of consecutive identical letters — it's « aaa », and the beauty of the line « qwerqwer » is equal to 1 because all adjacent letters in it are different.

To entertain Denis, Roma wrote him n lines p₁,p₂, p₃, ... ,p_n and asked him to calculate the beauty of the string (...((p₁·p₂)·p₃)· ;...)p_n. Denis did not fully understand how Roma's multiplication works, but he does not want to admit it, so he asks you to calculate the beauty of this line. Roma knows that Denis is too impressionable, so he guarantees that the beauty of the resulting string does not exceed 10⁹.

Input
The first line contains the number n (1 ≤ n ≤ 100000) — the number of lines Roma wrote.

The next n lines contain non-empty strings p₁, p₂, ..., p_n, consisting of lowercase English letters.

It is guaranteed that the total length of the strings does not exceed 100000, and also that the beauty of the product of all strings does not exceed 10⁹.

Imprint
Print a single integer — the beauty of the product of lines.
 

Examples

#	Input	Output	Explanations
1	3 a b a	3	The product of three lines is « abaaba »
2	2 bn a	1	The product of two strings is « abanana»