## K-Palindromes

A string is a \(k\)-palindrome iff it can be turned into a palindrome by deleting exactly \(k\) characters. For example, the string `CABBCAD`

is a 3-palindrome, since `D`

and both `C`

characters could be deleted to form `ABBA`

. On the other hand,`CCCXCC`

is a 1-palindrome, since the first `C`

could be deleted to get `CCXCC`

. Note that deleting the `X`

would also yield a palindrome. Further, `CCCXCC`

is also a 2-palindrome, since one could delete the `X`

, then any `C`

to get a palindrome.

Can you find the minimum \(k\) such that some string is a \(k\)-palindrome?

#### Input Specification

The first line contains an integer \(T\), the number of test cases to follow. The next \(T\) lines each contain a string \(S\) containing only uppercase English letters. Each such line defines a test case.

#### Output Specification

For each test case, output a single line containing a single integer. The minimum \(k\) such that the test case's string is a \(k\)-palindrome.

#### Bounds

Note this problem includes sub-problems of increasing difficulty worth different numbers of points:

- 40 points: \(1 \leq |S| \leq 10\)
- 100 points: \(1 \leq |S| \leq 2000\)

For all sub-problems:

\(1 \leq T \leq 10\)

#### Sample Input

```
4
CABBCAD
CCCXCC
A
TOPKEKGOODMEME
```

#### Sample Output

```
3
1
0
9
```

## Comments