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
CABBCAD
CCCXCC
A

Sample Output

3
1
0