Minimum Insertions to Make a Palindrome

Given a string STR of length N composed of lowercase English letters, your task is to determine the minimum number of characters that need to be added to make the string a palindrome.

Explanation:

You can insert characters at any position in the string, including the beginning, between any two characters, or at the end of the string.

Input:

The first line contains an integer 'T', representing the number of test cases. Each of the next T lines contains a string 'STR'.

Output:

For each test case, output the minimum number of characters required to make the string a palindrome on a new line.

Example:

Input:
2
deed
abb
Output:
0
1

Explanation: The string “deed” is already a palindrome, so no additional characters are needed. For the string “abb”, adding 'a' results in “abba”, which is a palindrome, thus requiring only 1 additional character.

Constraints:

• 1 <= T <= 10²
• 1 <= N <= 10⁴
• The string 'STR' consists only of lowercase English letters.

Time limit: 1 second