KiKoS is a fan of the TV series "How I Met Your Mother". Recently, he discovered a Spotify playlist with its soundtrack.

Alongside the undeniable hits "Let's Go to the Mall" and "Nothing Suits Me Like a Suit", he found a very goofy song: "Bang bang bangity bang". This is basically the only phrase in the entire song. To make it longer, you just say the same line, but prepend "I said" at the beginning, and then you can sing the whole thing again.

As a newbie songwriter, KiKoS wants to reuse this structure for a new song. Formally, given a non-empty word $\mathbb{S}$ consisting of lowercase English letters, the $\mathbb{S}$-song is composed of a block of two lines that can be repeated multiple times using the same word $\mathbb{S}$. Each block looks like:

$$ \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} $$

Given a large multiline text, determine the maximum possible amount of characters in some sequence of consecutive blocks that forms a valid song.

Input

The input consists of multiple lines, consisting of lowercase English letters, commas, and spaces. Each line ends with a newline character. The total number of characters including endlines does not exceed $10^5$.

There are no empty lines, and lines do not start or end with a space.

Output

Print a single integer: the maximum possible amount of characters in some consecutive sequence of blocks that matches the song pattern. This includes newline characters at the end of each line of the sequence, including the last line of the song. Each newline is considered to be $1$ character: pay attention to this if you have a Windows setup.

If there are no blocks matching the song pattern, output $-1$.

Examples

Input 1

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

Output 1

55

Input 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

Output 2

110

Input 3

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

Output 3

-1