Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Required String

By subhashis_cse · Limits 1s, 512 MB

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

InputOutput
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.

    Discussion

    Statistics


    88% Solution Ratio

    ridzz007Earliest, 2M ago

    CODER_RAFINFastest, 0.0s

    RAKIBULHOSSAINLightest, 262 kB

    nasibsuShortest, 611B

    Submit

    Login to submit