Alice recently developed a love for palindromes. She has got a number of strings available with herself. Alice gives one such string to Bob and challenges him to tell the smallest length of any substring required to be reversed so that after reversing that substring, the resulting string has at least one palindromic substring of length >= 2.
Help Bob 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 FORMAT:
First line contains T denoting the number of test cases.
First and the only line of each test case contains a string S.
Each string consists of lowercase English alphabets.
OUTPUT FORMAT:
For each test case, output in a new line the required answer.
CONSTRAINTS:
1≤T≤10
For 100% score - 2≤|S|≤105
For 20% score - 2≤|S|≤100
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.
Note that it is possible to satisfy the condition by reversing any other substring of length 2 also.
For Sample 2:
The given input string "xyx" is already a palindrome. Hence Bob does not need to do any reversal.
