CF1466C.Canine poetry

After his wife's tragic death, Eurydice, Orpheus descended to the realm of death to see her. Reaching its gates was uneasy, but passing through them proved to be even more challenging. Mostly because of Cerberus, the three-headed hound of Hades.

Orpheus, a famous poet, and musician plans to calm Cerberus with his poetry and safely walk past him. He created a very peculiar poem for Cerberus. It consists only of lowercase English letters.

We call a poem's substring a palindrome if and only if it reads the same backwards and forwards. A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deleting several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.

Unfortunately, Cerberus dislikes palindromes of length greater than $1$. For example in the poem abaa the hound of Hades wouldn't like substrings aba and aa.

Orpheus can only calm Cerberus if the hound likes his poetry. That's why he wants to change his poem so that it does not contain any palindrome substrings of length greater than $1$.

Orpheus can modify the poem by replacing a letter at any position with any lowercase English letter. He can use this operation arbitrarily many times (possibly zero). Since there can be many palindromes in his poem, he may have to make some corrections. But how many, exactly? Given the poem, determine the minimal number of letters that have to be changed so that the poem does not contain any palindromes of length greater than $1$.

在妻子欧律狄刻不幸离世后，俄耳甫斯 descend 到了冥界以再见她一面。抵达冥界之门已属不易，而穿过这扇门则更加艰难——主要原因在于哈迪斯的三头犬刻耳柏洛斯。

俄耳甫斯是一位著名的诗人兼音乐家，他计划用诗歌安抚刻耳柏洛斯，从而安然通过其守卫的门户。他为刻耳柏洛斯创作了一首极为特殊的诗，该诗仅由小写英文字母组成。

我们称一首诗的一个子串为回文串，当且仅当它正读与反读完全相同。字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可通过从 $b$ 的开头删除若干（可能为零个或全部）字符、并从 $b$ 的末尾删除若干（可能为零个或全部）字符而得到。

不幸的是，刻耳柏洛斯厌恶长度大于 $1$ 的回文子串。例如，在诗 abaa 中，这位冥界之犬将反感子串 aba 和 aa。

只有当刻耳柏洛斯喜欢他的诗时，俄耳甫斯才能成功安抚它。因此，他希望修改自己的诗，使其不包含任何长度大于 $1$ 的回文子串。

俄耳甫斯可通过将任意位置上的字母替换成任意一个小写英文字母来修改这首诗。该操作可执行任意多次（包括零次）。由于诗中可能存在多个回文子串，他或许需要进行若干修正。但究竟最少需要修改多少个字母？给定原诗，请确定使诗中不包含任何长度大于 $1$ 的回文子串所需的最小修改次数。

The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^5$) denoting the number of test cases, then $t$ test cases follow.

The first and only line of each test case contains a non-empty string of lowercase English letters, Orpheus' poem.

The sum of the length of Orpheus' poems in all test cases will not exceed $10^5$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量，随后是 $t$ 个测试用例。

每个测试用例仅有一行，包含一个非空的、由小写英文字母组成的字符串，即奥尔甫斯的诗歌。

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

You should output $t$ lines, $i$-th line should contain a single integer, answer to the $i$-th test case.

你应该输出 $t$ 行，第 $i$ 行应包含一个整数，即第 $i$ 个测试用例的答案。

In the first test case, we can replace the third character with c and obtain a palindrome-less poem bacba.

In the second test case, we can replace the third character with d and obtain a palindrome-less poem abdac.

In the third test case, the initial poem already doesn't contain any palindromes, so Orpheus doesn't need to change anything there.

在第一个测试用例中，我们可以将第三个字符替换为 c，从而得到一首不含回文的诗 bacba。

在第二个测试用例中，我们可以将第三个字符替换为 d，从而得到一首不含回文的诗 abdac。

在第三个测试用例中，初始的诗本身已不包含任何回文，因此奥尔甫斯无需进行任何修改。