Minimum Deletions to Form a Palindrome

Given a string s, your task is to determine the minimum number of characters that need to be removed to make s a palindrome.

A palindrome is a string that reads the same backward as forward. One strategy to solve the problem is to compute the longest palindromic subsequence (LPS) of the string. The minimum number of deletions required is given by:

\(\text{deletions} = n - \text{LPS}(s)\)

where \(n\) is the length of the string. Use dynamic programming to calculate the LPS.

inputFormat

The first line of the input contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a non-empty string \(s\) composed of lowercase English letters.

outputFormat

For each test case, output a single integer on a separate line which is the minimum number of deletions required to make the string a palindrome.

## sample

2
abca
racecar

1
0

</p>