Shouting is fun, but not everyone can do it well. It is really difficult to know which words are real intimidating shouts like "sianottootto" (used by brave warriors like our friend Hashmat) or which words are just ordinary screams with no effect whatsoever, like "rowrowtugboat" (used by angry orcs for yelling at their axes).

The researchers in Middle Earth Technical University showed that the intimidation of a word (could be a real shout or a scream) is connected with the warrior's ability to pronounce words backwards. Namely, the intimidation of a word is the length of the maximum subword of the form \[ww^{R}ww^{R}\] If no such subword exists, then the intimidation of the word is 0. For example, the intimidation of "zamarullurammarulluram" is 20 as it contains "marullurammarulluram" and the intimidation of "imbicanco" is 0. We can see that intimidation 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 \(\mathbf{T}\) denoting the number of test cases. Then \(\mathbf{T}\) test cases follow, each conforming to the format described below.

The input is one line containing a word, consisting of (uppercase or lowercase) letters of the English alphabet.

Batch #1:

• \(1 \leq \mathbf{T} \leq 100\)
• \(1 \leq \mathbf{len(A_i)} \leq 100\)

Batch #2:

• \(1 \leq \mathbf{T} \leq 5000\)
• \(1 \leq \mathbf{len(A_i)} \leq 5000\)

Output

You should output one integer \(\mathbf{K}\), the intimidation of the word, for each test case.

Samples

Input:

2
zamarullurammarulluram
imbicanco

Output:

20
0

Input:

3
appaappayipyip
zzzz
wololo

Output:

8
4
0