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
```