Minimum Removals to Make Palindrome

You are given t test cases. Each test case consists of a single non-empty string s. Your task is to determine the minimum number of characters that need to be removed from s so that it becomes a palindrome.

A palindrome is a string that reads the same backward as forward. For example, the string "racecar" is a palindrome. To solve this problem, you can use dynamic programming. Define a 2D array \(dp[i][j]\) which represents the minimum number of removals required to turn the substring \(s[i\ldots j]\) into a palindrome. The recurrence relation is given as:

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

Implement the solution so that for each test case, you print the minimum removals on a new line. All input will be taken from standard input and all output should be written to standard output.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (t) representing the number of test cases. Each of the next (t) lines contains a non-empty string (s).

outputFormat

For each test case, output on a new line a single integer representing the minimum number of character removals required to convert the string into a palindrome.## sample

4
abca
abcba
abcd
a

1
0
3
0