← 返回题目列表

Codeforces · 1466/C

C. 犬诗

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

在他的妻子尤律狄刻不幸去世后,俄耳甫斯下到死亡王国去看她。到达大门并不容易,但穿过大门却更具挑战性。主要是因为哈迪斯的三头猎犬刻耳柏洛斯。

著名诗人兼音乐家奥尔菲斯计划用他的诗歌安抚塞伯鲁斯并安全地从他身边走过。他为塞伯鲁斯创作了一首非常奇特的诗。它仅由小写英文字母组成。

当且仅当一首诗的子串前后读起来相同时,我们才称其为回文。字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 中删除几个(可能是零个或全部)字符并从末尾删除几个(可能是零个或全部)字符来获得。

不幸的是,Cerberus 不喜欢长度大于 $$$1$$$ 的回文。例如,在诗 abaa 中,哈迪斯的猎犬不喜欢子串 aba 和 aa。

只有当猎犬喜欢他的诗歌时,奥菲斯才能安抚刻耳柏洛斯。这就是为什么他想改变他的诗,使其不包含任何长度大于 $$$1$$$ 的回文子串。

Orpheus可以通过用任意小写英文字母替换任意位置的字母来修改这首诗。他可以任意多次使用此操作(可能为零)。由于他的诗中可能有很多回文,他可能需要做出一些更正。但到底有多少呢?给定这首诗,确定必须更改的最小字母数,以便这首诗不包含任何长度大于 $$$1$$$ 的回文。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) 表示测试用例的数量,然后是 $$$t$$$ 测试用例。

每个测试用例的第一行也是唯一一行包含一个非空的小写英文字母字符串,即奥菲斯的诗。

所有测试用例中奥菲斯诗歌的长度总和不会超过$$$10^5$$$。

输出

您应该输出 $$$t$$$ 行,第 $$$i$$$ 行应包含单个整数,回答第 $$$i$$$ 测试用例。

示例

输入 #1

7
babba
abaac
codeforces
zeroorez
abcdcba
bbbbbbb
a

输出 #1

1
1
0
1
1
4
0

注意

在第一个测试用例中,我们可以用 c 替换第三个字符并获得无回文诗 bacba。

在第二个测试用例中,我们可以将第三个字符替换为 d 并获得无回文诗 abdac。

在第三个测试用例中,最初的诗已经不包含任何回文,因此 Orpheus 不需要在那里更改任何内容。