codeforces#P1825A. LuoTianyi and the Palindrome String

LuoTianyi and the Palindrome String

Description

LuoTianyi gives you a palindrome^{\dagger} string ss, and she wants you to find out the length of the longest non-empty subsequence^{\ddagger} of ss which is not a palindrome string. If there is no such subsequence, output 1-1 instead.

^{\dagger} A palindrome is a string that reads the same backward as forward. For example, strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

^{\ddagger} A string aa is a subsequence of a string bb if aa can be obtained from bb by deletion of several (possibly, zero or all) characters from bb. For example, strings "a", "aaa", "bab" are subsequences of string "abaab", but strings "codeforces", "bbb", "h" are not.

Each test consists of multiple test cases. The first line contains a single integer tt (1t10001 \le t \le 1000) — the number of test cases. The description of test cases follows.

The first and the only line of each test case contains a single string ss (1s501 \le |s| \le 50) consisting of lowercase English letters — the string that LuoTianyi gives you. It's guaranteed that ss is a palindrome string.

For each test case, output a single integer — the length of the longest non-empty subsequence which is not a palindrome string. If there is no such subsequence, output 1-1.

Input

Each test consists of multiple test cases. The first line contains a single integer tt (1t10001 \le t \le 1000) — the number of test cases. The description of test cases follows.

The first and the only line of each test case contains a single string ss (1s501 \le |s| \le 50) consisting of lowercase English letters — the string that LuoTianyi gives you. It's guaranteed that ss is a palindrome string.

Output

For each test case, output a single integer — the length of the longest non-empty subsequence which is not a palindrome string. If there is no such subsequence, output 1-1.

输入数据 1

4
abacaba
aaa
codeforcesecrofedoc
lol

输出数据 1

6
-1
18
2

Note

In the first test case, "abcaba" is a subsequence of "abacaba" as we can delete the third letter of "abacaba" to get "abcaba", and "abcaba" is not a palindrome string. We can prove that "abcaba" is an example of the longest subsequences of "abacaba" that isn't palindrome, so that the answer is 66.

In the second test case, we can only get "a" and "aa", but they are all palindrome strings, so the answer is 1-1.