When babies babble they say things like GAGAGOOGOO or BABABABA. For the purposes of this question, we will define a baby talk word to be any non-empty string of letters which can be divided into two equal-length portions in such a way that the first portion is identical to the second.

Based on that definition, the following strings are words in baby talk: GAGA, GOOGOO, BABA, GUBBAGUBBA, DOGGIEDOGGIE, FDSFDS, IWANTMOREMILKIWANTMOREMILK and XX.

The following strings are not words in baby talk: BABAB, GAGOO, BA, DOGGIE and X.

Based on this definition, the string GAGAGOOGOO is actually two baby talk words concatenated together. The string BABABABA could be a single baby talk word or it could be two baby talk words, depending on how you choose to divide it.

The input will contain ~10~ test cases. Each test case consists of a single line of text containing a string of capital letter characters of length ~N~ ~(1 \le N \le 2000)~. Your job is to find the longest substring consisting only of consecutive baby talk words, as defined above, and report the length of that substring on a single line. In the test cases below, the longest baby talk string in each input string is underlined.

Sample Input

GOOGOOGAGA
BABABABA
PTHHPTHHBAGOOGOOGAGABOOOOO
XYBABABABAXYX
GOOGOOGAGAGAGAGOOOGAGAGOOO
BABABABABA
CUTEBABYTALKSTRING
CCEEKCKCBFBFEEBABAFKFKAADDDAAKKBBEEIIHHDDGGIIEEIIDDHHGGBBHHKKJJHHCCAAJJDDDAAKKBB
IEIEFFFFAAJJBBJJJ
BBHHBBBBFFBGGEEEEEEHHAAIIACC

Sample Output

10
8
10
8
26
8
0
48
16
14

Question Development Team

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org