Make Palindrome Problem Statement

You are provided with a string STR of length N comprising lowercase English alphabet letters. Your task is to determine and return the minimum number of characters that need to be added at the beginning of the string to make it a palindrome.

Input:

The first line contains an integer 'T' indicating the number of test cases. Each test case is given in a single line containing the string STR.

Output:

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

Example:

Input:
T = 2
STR = "deed"
STR = "aabaaca"

Output:
0
2

Constraints:

• 1 <= T <= 100
• 1 <= N <= 5000
• STR contains only lowercase English letters.
• Time limit: 1 second

Note:

Implementation should focus on determining the function to calculate the required number without outputting results directly.