Minimum Additions to Form a Palindrome

You are given a string s. Your task is to determine the minimum number of characters that need to be added at the beginning of s in order to make it a palindrome.

A string is a palindrome if it reads the same backward as forward. Formally, given a string \( s \) of length \( n \), you need to find the smallest non-negative integer \( k \) such that when you prepend a string of length \( k \) (which is typically the reverse of a prefix of \( s \)) to s, the resulting string is a palindrome.

Hint: One way to solve this problem is to check for each index \( i \) (starting from 0) whether the substring \( s[i:] \) is a palindrome. The answer will then be \( i \) when the condition is satisfied.

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases. The first line contains a single integer \( T \), the number of test cases. Each of the following \( T \) lines contains a non-empty string s.

For example:

3
ab
racecar
abc

outputFormat

For each test case, output a single integer on a new line representing the minimum number of characters that need to be added to the beginning of the string s to make it a palindrome.

For example, the corresponding output for the input above would be:

1
0
2

## sample

3
ab
racecar
abc

1
0
2

</p>