Given a string s, find the minimum number of characters you need to insert at the beginning in order to make the string a palindrome.

Example 1

s: “baaba”

Result: 1

Example 2

s: “bab”

Result: 0

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of the test cases.

For each test case, the input has one line with the string ‘s’.

Output Format

For each test case, the output has one line with an integer ‘val’ denoting the minimum number of characters to insert.

Sample Input

2
a
abc

Expected Output

0
2

Constraints

1 <= T <= 100
1 <= s length <= 10000
The characters of strings are lowercase English alphabets.