A string is called a \(Good\) string if it has the following properties:
- The length of the string is >=2
- The first and the last character of the string are identical.
- \( Operation 1\): Remove a letter from the beginning of the string.
- \(Operation2\): Remove a letter from the end of the string.
You can apply the \(Operation1\) or \(Operation2\) or both on the string S. Now your task is to find out the minimum number of operations to make the string S a \(Good\) string.
Input:
The first line of the input will contain T , the number of testcases.
Next line will contain a string of a certain length. The string will consist of only lower case letters from 'a' to 'z'.
Output:
Print the minimum no of operations required. If impossible print "-1", without quotes .
Constraints:
- \(1 \le T \le 100\)
- \(2 \le N \le 10^4\)
For 1st test case:
The string is \(abcda\) , we don't need to do any operations as the the string is already satisfying the criteria
For 2nd test case:
Here we have two options either remove the last b and make the string \(abcdefghia\) ,
or remove the first a and make the original string \(bcdefghiab\) , hence we need only 1 operation.
For 3rd test case:
No \(Good\) string could be made
For 4th test case:
Remove the b from the beginning , and remove p , o , l from the end to make the string \(acdefghipa\) (a \(Good\) string ) hence total no of operations= \( 1+3=4\).
