Задача . E. Произведение строк

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