Minimum Insertions to Form a Palindrome

Given a string s, your task is to compute the minimum number of characters that must be inserted to transform s into a palindrome. A palindrome is a string that reads the same forwards and backwards.

You are allowed to insert characters at any position in the original string. The optimal solution can be computed using dynamic programming. Specifically, you may consider the following recurrence relation:

$$ dp[i][j]= \begin{cases} 0 & \text{if } i \ge 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 program should read input from stdin and print the result for each test case to stdout.

inputFormat

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

T
s1 s2 ... sT

Here, the first line contains an integer T denoting the number of test cases. The following tokens (separated by whitespace) are the strings for which you need to compute the minimum number of insertions to make them palindromes.

outputFormat

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

## sample

1
race

3

</p>