310381: CF1825A. LuoTianyi and the Palindrome String

A. LuoTianyi and the Palindrome Stringtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

LuoTianyi gives you a palindrome$^{\dagger}$ string $s$, and she wants you to find out the length of the longest non-empty subsequence$^{\ddagger}$ of $s$ which is not a palindrome string. If there is no such subsequence, output $-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 $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from $b$. For example, strings "a", "aaa", "bab" are subsequences of string "abaab", but strings "codeforces", "bbb", "h" are not.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \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 $s$ ($1 \le |s| \le 50$) consisting of lowercase English letters — the string that LuoTianyi gives you. It's guaranteed that $s$ 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$.

ExampleInput

4
abacaba
aaa
codeforcesecrofedoc
lol

Output

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 $6$.

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

题目大意：
洛天依给你一个回文字符串 s，要求你找出 s 的最长非空子序列，该子序列不是回文字符串。如果不存在这样的子序列，则输出 -1。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 1000）—— 测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个字符串 s（1 ≤ |s| ≤ 50），由小写英文字母组成，这是洛天依给你的字符串。保证 s 是一个回文字符串。

输出数据格式：
对于每个测试用例，输出一个整数——最长的非空子序列的长度，该子序列不是回文字符串。如果不存在这样的子序列，则输出 -1。

示例：
输入
```
4
abacaba
aaa
codeforcesecrofedoc
lol
```
输出
```
6
-1
18
2
```

注意：
在第一个测试用例中，"abcaba" 是 "abacaba" 的子序列，我们可以删除 "abacaba" 的第三个字符得到 "abcaba"，且 "abcaba" 不是回文字符串。我们可以证明 "abcaba" 是 "abacaba" 的最长非回文子序列的一个例子，因此答案是 6。
在第二个测试用例中，我们只能得到 "a" 和 "aa"，但它们都是回文字符串，所以答案是 -1。题目大意： 洛天依给你一个回文字符串 s，要求你找出 s 的最长非空子序列，该子序列不是回文字符串。如果不存在这样的子序列，则输出 -1。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 1000）—— 测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个字符串 s（1 ≤ |s| ≤ 50），由小写英文字母组成，这是洛天依给你的字符串。保证 s 是一个回文字符串。 输出数据格式： 对于每个测试用例，输出一个整数——最长的非空子序列的长度，该子序列不是回文字符串。如果不存在这样的子序列，则输出 -1。 示例： 输入 ``` 4 abacaba aaa codeforcesecrofedoc lol ``` 输出 ``` 6 -1 18 2 ``` 注意： 在第一个测试用例中，"abcaba" 是 "abacaba" 的子序列，我们可以删除 "abacaba" 的第三个字符得到 "abcaba"，且 "abcaba" 不是回文字符串。我们可以证明 "abcaba" 是 "abacaba" 的最长非回文子序列的一个例子，因此答案是 6。 在第二个测试用例中，我们只能得到 "a" 和 "aa"，但它们都是回文字符串，所以答案是 -1。