Minimum Insertions or Deletions to Palindrome

Given a string \( s \), your task is to transform it into a palindrome using the minimum number of insertions or deletions. A palindrome is a string that reads the same forwards and backwards. This problem can be approached using the concept of the Longest Common Subsequence (LCS) between the string and its reverse. The minimum number of modifications required is given by:

[ \text{result} = |s| - \text{LCS}(s, s^R), ]

where \( s^R \) denotes the reverse of string \( s \) and \(|s|\) is the length of \( s \).

The input will consist of multiple test cases. For each test case, output the minimum number of modifications needed on a new line.

inputFormat

The first line contains an integer \( T \) (\(1 \leq T \leq 10^5\)), the number of test cases. Each of the following \( T \) lines contains a non-empty string \( s \) consisting of lowercase English letters.

outputFormat

For each test case, output a single integer --- the minimum number of insertions or deletions required to transform the string \( s \) into a palindrome. Each result should be printed on a new line.

## sample

3
abc
racecar
xyz

2
0
2

</p>