Рома и Денис отправились на соревнование по программированию. В долгой дороге ребята заскучали, поэтому решили придумать что-нибудь интересное. Рома придумал рецепт вкусной пиццы, а Денис придумал операцию умножения строк. По версии Дениса, произведением строки $$$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$$$.