# Casting Spells

Time Limit: 10 Seconds Memory Limit: 131072 KB

Casting spells is the least understood technique of dealing with real life. Actually, people find it quite hard to distinguish between a real spells like "abrahellehhelleh" (used in the battles and taught at the mage universities) and screams like "rachelhellabracadabra" (used by uneducated witches for shouting at cats).

Finally, the research conducted at the Unheard University showed how one
can measure the power of a word (be it a real spell or a scream). It
appeared that it is connected with the mages' ability to pronounce words
backwards. (Actually, some singers were burned at the stake for exactly
the same ability, as it was perceived as demonic possession.) Namely, the
power of a word is the length of the maximum subword of the form *ww*^{R}*ww*^{R} (where *w* is an arbitrary sequence of characters and
*w*^{R} is *w* written backwards). If no such subword exists, then the
power of the word is 0. For example, the power of `abrahellehhelleh`
is 12 as it contains hellehhelleh and the power of
`rachelhellabracadabra` is 0. Note that the power of a word is
always a multiple of 4.

## Input

The input contains several test cases. The first line of the input contains
a positive integer *Z* <= 40, denoting the number of test cases. Then
*Z* test cases follow, each conforming to the format described below.

The input is one line containing a word of length at most
3*10^{5},
consisting of (large or small) letters of the English alphabet.

## Output

For each test case, your program has to write an output conforming to the format described below.

You should output one integer *k* being the power of the word.

## Sample Input

2 abrahellehhelleh rachelhellabracadabra

## Sample Output

12 0Submit

Source: Central European Regional Contest 2010