Rajib recently developed a nice game in which he worked on palindromes. Rajib told Raihan to play his game.
Rajib gives one such string to Raihan and challenges him to tell the smallest length of any substring required to be reversed so that after reversing that substring ,where the resulting string has at least one palindromic substring of length >= 2
Help Raihan to find the smallest length of the substring to be reversed.
If the string already contains a palindromic substring, print 0.
If it is not possible to obtain a palindromic substring by any reversal, then print −1.
Input
First line contains T denoting the number of test cases. (1<=T<=10).
First and the only line of each test case contains a string S. (2<=|s|<=10^5)
Each string consists of lowercase English alphabets.
Output
For each test case print he required answer.
Do not forget to print a new line after each case.
Sample
| Input | Output |
|---|---|
2 abcdba xyx | 2 0 |
For Sample 1:
Given string is "abcdba" which does not contain a palindromic substring.
If we reverse the substring "bc", the resulting string is "acbdba" which contains "bdb" as a palindromic substring. Hence the answer is 2 since it is the smallest possible reversal.
For Sample 2:
The given input string "xyx" is already a palindrome. So no need to do any reversal.
