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