Roman 和 Denis 正在前往参加编程比赛。由于旅途漫长,他们很快就感到无聊,因此决定想出点办法。罗曼发明了披萨的食谱,而丹尼斯发明了字符串乘法。根据 Denis 的说法,长度为 $$$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$$$ 的乘积。
Roman 嫉妒 Denis,因为他发明了如此酷的操作,因此决定也发明一些与字符串相关的东西。由于罗曼是个爱美的人,他决定将字符串的美度定义为最长的子字符串的长度,该子字符串仅由一个字母组成。例如,字符串“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$$$ 的乘法。Roman 还没有完全意识到 Denis 的乘法是如何工作的,所以他向你寻求帮助,Denis 知道,Roman 很容易受影响,他保证,结果字符串的美丽度最多为 $$$10^9$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — 字符串的数量,由 Denis 编写。
接下来的 $$$n$$$ 行包含非空字符串 $$$p_1, p_2, \ldots, p_n$$$,由小写英文字母组成。
可以保证,字符串 $$$p_i$$$ 的总长度最多为 $$$100\,000$$$,而最终产品的美妙之处在于最多为 $$$10^9$$$。
输出
精确打印一个整数——字符串乘积的美妙之处。
示例
输入 #1
3 a b a
输出 #1
3
输入 #2
2 bnn a
输出 #2
1
注意
在第一个示例中,字符串的乘积等于“abaaaba”。
在第二个示例中,字符串的乘积等于“abanana”。