Minimum Steps to Make Palindrome

You are given a string S. The task is to determine the minimum number of insertions required to convert S into a palindrome. A palindrome is a string that reads the same forwards and backwards.

Consider the following definition in terms of dynamic programming. Let \( dp[i][j] \) denote the minimum number of insertions needed to convert the substring \( S[i \ldots j] \) into a palindrome. The recurrence is given by:

\( dp[i][j] = \begin{cases} 0 & \text{if } i \geq j, \\ dp[i+1][j-1] & \text{if } S[i] = S[j], \\ \min(dp[i+1][j], dp[i][j-1]) + 1 & \text{if } S[i] \neq S[j]. \end{cases} \)

Your job is to implement a program that, given multiple test cases, calculates and prints the minimum number of insertions required for each string.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer T, the number of test cases.
• Each of the next T lines contains a non-empty string S composed of lowercase letters.

outputFormat

For each test case, output on a new line a single integer representing the minimum number of insertions required to convert the given string into a palindrome.## sample

4
abba
abc
race
abcd

0
2
3
3