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?
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.
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.
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\)
4 CABBCAD CCCXCC A TOPKEKGOODMEME
3 1 0 9