Minimum Removal to Form Palindrome

You are given a string and your task is to determine the minimum number of characters that must be removed from the string so that the remaining characters form a non-empty palindrome.

A palindrome is a string that reads the same forward and backward. You can obtain a palindrome by removing some characters (possibly none) from the original string. The required answer is the difference between the length of the original string and the length of its longest palindromic subsequence (LPS). In mathematical terms, if the length of the string is n and the length of the LPS is LPS, then the answer is given by:

$$ answer = n - LPS. $$

Your task is to compute this value for each given test case.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains an integer T, representing the number of test cases.
2. The following T lines each contain a single non-empty string consisting of lowercase English letters.

It is guaranteed that each string is non-empty.

outputFormat

For each test case, output a single integer on a new line that represents the minimum number of characters to remove from the given string in order to obtain a non-empty palindrome.

## sample

3
abcdcba
abca
deed

0
1
0

</p>