← 返回题目列表

Codeforces · 1800/D

D. 删除两个字母

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

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$$$。

输出

对于每个测试用例,打印一个整数——通过删除两个连续字母可以获得的不同字符串的数量。

示例

输入 #1

7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa

输出 #1

4
1
5
3
3
3
1

注意

第一个示例在语句中进行了解释。

在第三个示例中,获得以下字符串:“cdef”、“adef”、“abef”、“abcf”、“abcd”。

在第七个示例中,任何删除都将产生字符串“aba”。