A string is called a $$Good$$ string if it has the following properties:
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.
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'.
Print the minimum no of operations required. If impossible print "-1", without quotes .
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$$.