CF1800D Remove Two Letters

Dmitry 有一个字符串 $s$，由小写拉丁字母组成。 Dmitry 决定从字符串 $s$ 中删除两个连续的字符，你想知道经过这样的操作后可以得到多少个不同的字符串。 例如，Dmitry 有字符串 "aaabcc"。你可以得到如下不同的字符串："abcc"（删除第一个和第二个或第二个和第三个字符）、"aacc"（删除第三个和第四个字符）、"aaac"（删除第四个和第五个字符）以及 "aaab"（删除最后两个字符）。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示通过删除两个连续字母可以得到的不同字符串的数量。

第一个样例的解释见题面。 在第三个样例中，可以得到如下字符串："cdef"、"adef"、"abef"、"abcf"、"abcd"。 在第七个样例中，无论怎么删除，最终得到的字符串都是 "aba"。 由 ChatGPT 4.1 翻译