Minimum Operations to Convert String to Palindrome

Given an integer T and T test cases, each consisting of a string S, determine the minimum number of operations required to transform S into a palindrome.

A string S is called a palindrome if it reads the same backward as forward. In other words, S is a palindrome if

\( S = S^R \)

where \( S^R \) is the reverse of \( S \).

In a single operation, you are allowed to replace, insert, or delete a character. The objective is to achieve a palindrome with the minimum number of operations.

inputFormat

The first line contains an integer T indicating the number of test cases.

Each of the following T lines contains a string S consisting of lowercase letters.

outputFormat

For each test case, output a single integer representing the minimum number of operations required to convert S into a palindrome. Each answer should be printed on a new line.

## sample

3
abc
racecar
abca

1
0
1

</p>