CF1466C Canine poetry

在妻子 Eurydice 悲惨去世后，Orpheus 下到冥界去见她。到达冥界大门并不容易，而通过大门则更加艰难。这主要是因为冥界的三头犬 Cerberus。 Orpheus 是著名的诗人和音乐家，他打算用自己的诗歌安抚 Cerberus，从而安全地通过。他为 Cerberus 创作了一首非常独特的诗，这首诗只包含小写英文字母。 我们称一首诗的子串为回文串，当且仅当它正着读和反着读都相同。如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符，并从结尾删除若干（可能为零或全部）字符得到，那么 $a$ 是 $b$ 的子串。 不幸的是，Cerberus 不喜欢长度大于 $1$ 的回文串。例如，在诗句 abaa 中，冥界三头犬不喜欢子串 aba 和 aa。 Orpheus 只有在 Cerberus 喜欢他的诗歌时才能安抚它。因此，他想要修改自己的诗，使其不包含任何长度大于 $1$ 的回文子串。 Orpheus 可以通过将任意位置的字母替换为任意小写英文字母来修改诗歌。他可以无限次（可能为零次）使用这种操作。由于诗中可能存在许多回文串，他可能需要进行一些修改。那么，究竟需要最少修改多少个字母，才能使诗歌不包含任何长度大于 $1$ 的回文子串？ 给定诗歌内容，请你计算最少需要修改多少个字母，使诗歌不包含任何长度大于 $1$ 的回文子串。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量，接下来有 $t$ 个测试用例。 每个测试用例的第一行包含一个非空的小写英文字母字符串，表示 Orpheus 的诗歌。 所有测试用例中 Orpheus 诗歌的总长度不超过 $10^5$。

输出 $t$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案，即最少需要修改的字母数。

在第一个测试用例中，我们可以将第三个字符替换为 c，得到不含回文串的诗 bacba。 在第二个测试用例中，我们可以将第三个字符替换为 d，得到不含回文串的诗 abdac。 在第三个测试用例中，原始诗歌已经不包含任何回文串，因此 Orpheus 不需要做任何修改。 由 ChatGPT 4.1 翻译