Minimum Operations to Palindrome

You are given a string s. Your task is to determine the minimum number of operations required to transform s into a palindrome. In each operation, you may insert a character at any position in the string. Equivalently, this value is also the minimum number of deletions required to form a palindrome. Formally, if dp(i, j) denotes the minimum number of operations required to transform the substring \(s[i\ldots j]\) into a palindrome, then:

[ 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} ]

Your program should handle multiple test cases.

inputFormat

The input begins with an integer T denoting the number of test cases. Each of the next T lines contains a single string s.

Constraints: The length of s is at least 1. It is guaranteed that s consists of lowercase English letters only.

outputFormat

For each test case, output a single integer representing the minimum number of operations required to transform the input string into a palindrome. Each result should be printed on a new line.

## sample

4
ab
abc
bbb
abcdedcba

1
2
0
0

</p>