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

### Statistics

91% Solution Ratio

ridzz007Earliest, Jan '21

S_SubrataFastest, 0.0s

RAKIBULHOSSAINLightest, 262 kB

nasibsuShortest, 611B

### Related Contests

 NCPC Team Selection Contest of IU - 2021 9M ago STP Coding Test 25 Jan 2021 Jan '21