Codeforces Round 872 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

strings

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. LuoTianyi and the Palindrome String

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLuoTianyi 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$$$.

Example

Input

4abacabaaaacodeforcesecrofedoclol

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 19:53:45 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|