← 返回题目列表

Codeforces · 1825/A

A. 洛天依与回文串

中文机器翻译题面 查看原题

洛天依给了你一个回文$$$^{\dagger}$$$字符串$$$s$$$,她要你找出$$$s$$$中最长的非回文字符串$$$^{\ddagger}$$$的长度。如果不存在这样的子序列,则输出$$$-1$$$。

$$$^{\dagger}$$$ 回文是向后读与向前读相同的字符串。例如,字符串“z”、“aaa”、“aba”、“abccba”是回文,但字符串“codeforces”、“reality”、“ab”则不是。

$$$^{\ddagger}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从 $$$b$$$ 中删除几个(可能是零个或全部)字符来从 $$$b$$$ 获得。例如,字符串“a”、“aaa”、“bab”是字符串“abaab”的子序列,但字符串“codeforces”、“bbb”、“h”不是。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含一个由小写英文字母组成的字符串 $$$s$$$ ($$$1 \le |s| \le 50$$$) — 这是 LuoTianyi 给你的字符串。保证 $$$s$$$ 是回文字符串。

输出

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

示例

输入 #1

4
abacaba
aaa
codeforcesecrofedoc
lol

输出 #1

6
-1
18
2

注意

在第一个测试用例中,“abcaba”是“abacaba”的子序列,因为我们可以删除“abacaba”的第三个字母来得到“abcaba”,并且“abcaba”不是回文字符串。我们可以证明“abcaba”是“abacaba”的最长子序列的一个例子,它不是回文,所以答案是$$$6$$$。

在第二个测试用例中,我们只能得到“a”和“aa”,但它们都是回文字符串,所以答案是$$$-1$$$。