Faster than Flash
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

There is a meta human in Central City. The Flash has been given velocity-9 drug by this meta which reduces his speed. In order to defeat this meta Harrison wells has found String S and code.

Consider following code written by Harrison wells :

boolean function(String str){

for(int i=0;i<str.length();i++){
for(int j=i+1;j<str.length();j++){
String sub=str.substring(i, j+1);
// sub is substring of s from ith to jth character
boolean flag=true;
for(int k=0;k<sub.length();k++){
if(sub.charAt(k)!=sub.charAt(sub.length()-k-1)){
flag=false;
}
}
if(flag) return false;
}
}
return true;
}


Now, Harrison Wells knows that the only way to defeat this meta is to find the longest substring of string S that has length greater than 1 and when given to the above function returns true.

Since this code is pretty slow and the Flash does not have enough speed to help central city. Help him to find the longest substring of the given input string which will return true when given to the above function. If there exists no such substring that has length greater than 1 then print -1.

Input

First line of input contains integer T , denoting number of test cases.

Each test case contains String S, which Harrison Wells has found.

Output

Print answer of each test case in new line.

Constrains

1<=T<=10

1<=|S|<=100000

SAMPLE INPUT
3
synapse
a
daiict
SAMPLE OUTPUT
7
-1
3
Explanation

In the first test case, synapse is the largest substring.

In the second test case, there is no substring has length greater then 1.

In the third test case, dai is the largest substring.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

This Problem was Asked in

Challenge Name

Code Mutants

OTHER PROBLEMS OF THIS CHALLENGE
Notifications