KiKoS jest fanem serialu telewizyjnego „How I Met Your Mother”. Niedawno odkrył na Spotify playlistę ze ścieżką dźwiękową z tego serialu.

Obok niekwestionowanych hitów „Let's Go to the Mall” oraz „Nothing Suits Me Like a Suit” znalazł bardzo zabawną piosenkę: „Bang bang bangity bang”. To w zasadzie jedyna fraza w całej piosence. Aby ją wydłużyć, wystarczy wypowiedzieć ten sam wers, ale dodać na początku „I said”, a potem można zaśpiewać całość od nowa.

Jako początkujący autor tekstów, KiKoS chce ponownie wykorzystać tę strukturę w nowej piosence. Formalnie, dla danego niepustego słowa $\mathbb{S}$ składającego się z małych liter alfabetu angielskiego, $\mathbb{S}$-piosenka składa się z bloku dwóch wierszy, który może być powtórzony wielokrotnie przy użyciu tego samego słowa $\mathbb{S}$. Każdy blok wygląda następująco:

$$ \begin{aligned} &\mathbb{S}\texttt{, }\mathbb{S}\texttt{ }\mathbb{S}\texttt{ity }\mathbb{S} \\ &\texttt{i said }\mathbb{S}\texttt{, }\mathbb{S}\texttt{ }\mathbb{S}\texttt{ity }\mathbb{S} \end{aligned} $$

Mając dany duży wielowierszowy tekst, wyznacz maksymalną możliwą liczbę znaków w pewnym ciągu kolejnych bloków, który tworzy poprawną piosenkę.

Wejście

Wejście składa się z wielu wierszy zawierających małe litery alfabetu angielskiego, przecinki i spacje. Każdy wiersz kończy się znakiem nowej linii. Łączna liczba znaków wraz ze znakami końca linii nie przekracza $10^5$.

Nie ma pustych wierszy, a wiersze nie zaczynają się ani nie kończą spacją.

Wyjście

Wypisz jedną liczbę całkowitą: maksymalną możliwą liczbę znaków w pewnym ciągu kolejnych bloków pasującym do wzorca piosenki. Obejmuje to znaki nowej linii na końcu każdego wiersza ciągu, włącznie z ostatnim wierszem piosenki. Każdy znak nowej linii jest liczony jako $1$ znak — zwróć na to uwagę, jeśli korzystasz z systemu Windows.

Jeśli żadne bloki nie pasują do wzorca piosenki, wypisz $-1$.

Przykład

Wejście 1

bang, bang bangity bang
i said bang, bang bangity bang

Wyjście 1

55

Wejście 2

bang, bang bangity bang
i said bang, bang bangity bang
bank, bank bankity bank
i said bank, bank bankity bank
bank, bank bankity bank
i said bank, bank bankity bank

Wyjście 2

110

Wejście 3

grandmasters are red,
experts are blue,
parsing problems are bad,
but we believe in you

Wyjście 3

-1