URI Online Judge | 2954

The Game

By Samuel Eduardo da Silva, IFSULDEMINAS/UFF BR Brazil

Timelimit: 1

If you are reading this problem, you have lost The Game. Yes, the rule of the Game is: if you remember the Game, you lose. Ethan Hawke was a boy who was intrigued by The Game, and wanted to figure out ways to stay as long as possible without losing, so he realized that in order to lose, it is enough that some of his friends say "Game" or "I lost" in their virtual conversations , that automatically it remembers and loses the Game, being able to be in capital letters or small letters. Ethan would like to calculate the time he wins the Game. The time calculation is as follows: Friends' conversations are virtual, and to read a letter, it takes 1 second, which special characters like punctuation and spaces are not considered. If at any point, the words that make Ethan lose appear, he loses the Game and the calculation resumes. For example, in the phrase: "I was playing a game yesterday, and it was good." Ethan won the game in: "I was playing a game". Totalizing 19 seconds in which he won (counting the letters). As the word "game" has appeared, it loses here and the time count resumes. And it continues to win in "yesterday, and it was good," for another 15 seconds. So the maximum time he was a winner was 19 seconds. The same would apply if the word "lost" appeared. Remembering that these two words will only make the person lose, if they are whole, and not sub words of others, because when this happens, people do not perceive them and thus do not lose the game. Given a list of phrases spoken by Ethan and his friends, indicate which was the longest time that he was able to win the game in each of them.

Input

The first line of the entry contains an integer N(0 < N ≤ 10), indicating the number of phrases spoken in the conversation. The next N lines contain the phrases spoken in the conversations of Ethan's friends.

Each sentence will contain a maximum of 100,000 characters, including letters, uppercase and lowercase letters, spaces, or punctuation (comma and period).

Output

The maximum number of time that Ethan has managed to remain the winner of the Game.

Input Sample Output Sample

2
O Jogo, o que dizer de o Jogo.
Estava jogando um jogo ontem, e ele era bom.

16
19