Minimum Deletions to Make a Palindrome

Given a string s, determine the minimum number of deletions required to transform it into a palindrome. A palindrome is a sequence that reads the same forwards and backwards. You can derive a solution using dynamic programming with the following recurrence relation:

\(dp[i][j] = \begin{cases} 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}\)

If the string is already a palindrome, then no deletions are required. Your task is to compute the minimum number of deletion operations needed for each test case.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a non-empty string \(s\), for which you need to compute the minimum number of deletions required to transform it into a palindrome.

outputFormat

For each test case, output a single line containing the minimum number of deletions needed to make the string a palindrome.

## sample

4
abc
abcd
aebcbda
racecar

2
3
2
0

</p>