Minimum Removals to Palindrome

Given a string S, determine the minimum number of characters that need to be removed so that the remaining string is a palindrome (i.e. reads the same forwards and backwards). A standard approach is to first find the length of the longest palindromic subsequence (LPS) of S and then compute the answer using the formula: $$\text{answer} = |S| - \text{LPS}.$$

Your task is to write a program that reads multiple test cases from standard input and for each test case, prints the minimum number of removals required.

Note: The input/output should be processed via standard input (stdin) and standard output (stdout), respectively.

inputFormat

The first line contains an integer T, the number of test cases. Each of the following T lines contains a single non-empty string.

outputFormat

For each test case, output a single line with an integer representing the minimum number of removals required to make the string a palindrome.

## sample

3
abc
aebcbda
racecar

2
2
0

</p>