A. Династические головоломки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Древние берляндцы считали, что чем длиннее имя, тем важнее человек, его носящий. Берляндские цари славились своими длинными именами. Но длинные имена — это несколько неудобно, поэтому берляндцы стали сокращать имена своих царей. Каждого царя они называли по первым буквам всех его имен. Например, царя, которого звали Великий Василий Пупкин, берляндцы всегда зовут ВВП.

В Берляндии за её долгую историю сменилось немало династий царей, но все они были объединены общими традициями. Так, согласно одной из берляндских традиций, для поддержания стабильности в государстве, первое имя наследника должно совпадать с последним именем предшественника (следовательно, первая буква сокращенного имени наследника совпадает с последней буквой сокращенного имени предшественника). Берляндцы очень ценят стабильность, поэтому эта традиция никогда не нарушалась. Еще берляндцы любят завершенность, поэтому еще одна традиция требует того, чтобы первое имя первого царя в династии совпадало с последним именем последнего царя в этой династии (следовательно первая буква сокращенного имени первого царя совпадает с последней буквой сокращенного имени последнего царя). Эта традиция, естественно, тоже всегда соблюдалась.

Название династии образуется по очень простым правилам: берутся все сокращенные имена царей в том порядке, в котором они правили, и выписываются в одну строчку. К примеру, династия из царей «аb» и «ba» называется «abba», а династия, в которой был только царь «abca», называется «abca».

Историк Вася недавно нашел список сокращенных имен всех берляндских царей и их родственников. Помогите Васе найти максимально длинное название династии, которая могла существовать в Берляндии.

Заметим, что в списке все имена упорядочены по времени, то есть если имя A идет в списке раньше, чем имя B, то если A и B были царями, то царь A правил раньше, чем царь B.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 5·105) — количество имен в списке Васи. В следующих n сроках записано n кратких имен по одному в строке. Краткое имя — это непустая последовательность маленьких латинских букв. Его длина не превосходит 10 символов.

Выходные данные

Выведите единственное число — длину названия искомой династии в буквах.

Если список Васи оказался неправильным и ни одной династии в нем найти нельзя, выведите единственное число 0.

Примеры
Входные данные
3
abc
ca
cba
Выходные данные
6
Входные данные
4
vvp
vvp
dam
vvp
Выходные данные
0
Входные данные
3
ab
c
def
Выходные данные
1
Примечание

В первом примере может существовать две династии: с названием «abcca» (в нее входят первый и второй цари) и с названием «abccba» (в нее входят первый и третий).

Во втором примере допустимых династий нет.

Единственная династия в третьем примере состоит из одного царя с именем «c».