Minimum Removals to Palindrome

You are given a string s. Your task is to determine the minimum number of characters that must be removed from s so that the resulting string becomes a palindrome.

A palindrome is a string that reads the same backward as forward. For example, the string "abb" can become a palindrome "bb" after removing one character, whereas "abc" requires two removals, and "racecar" is already a palindrome with 0 removals.

It is recommended to use a dynamic programming approach to solve this problem. One common method is to use a 2D DP array where dp[i][j] represents the minimum removals required for the substring from index i to j. The recurrence relation is given by:

\(dp[i][j] = \begin{cases} 0 & \text{if } i \geq j \\ dp[i+1][j-1] & \text{if } s[i] = s[j] \\ 1 + \min(dp[i+1][j],\ dp[i][j-1]) & \text{if } s[i] \neq s[j] \end{cases}\)

Implement the solution so that it reads input from stdin and writes output to stdout.

inputFormat

The first line of input contains an integer T, the number of test cases. Each of the next T lines contains a single string s.

You should read from stdin.

outputFormat

For each test case, output a single line containing the minimum number of characters that must be removed to make the input string a palindrome.

The output should be written to stdout.

## sample

2
abb
abc

1
2

</p>