Minimum Characters to Make a String Palindrome

Given a string STR of length N, determine the minimum number of characters to be added to the front of the string to make it a palindrome.

Input:

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

Output:

For each test case, output a single integer representing the minimum number of characters needed to make the string a palindrome, printed on a new line for each test case. 

Example:

Input:

2
deed
aabaaca

Output:

0
2

Explanation:

For the string "deed", it's already a palindrome, so no characters are needed. For "aabaaca", we need to add 'a' and 'c' to the front to form "acaabaaca", which is a palindrome.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 105
• STR contains only lowercase English letters.

Note: You do not need to output anything yourself. Implement the function to compute the required values.