## K-Palindromes

Points: 1 (partial)
Time limit: 3.0s
Python 12.0s
Memory limit: 512M

Author:
Problem type

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

3
A
3
0