No submission language available for this problem.

Background

Special for beginners, ^_^

Description

小 A 面前有一串小写字母组成的字符串 $s$ 。

小 A 决定从字符串 $s$ 中删除两个连续的字符，并想知道经过这样的操作可以得到多少个不同的字符串。

例如，有一个字符串 "aaabcc"。可以得到以下不同的字符串："abcc"（删除前两个或第二个和第三个字符）、"aacc"（删除第三个和第四个字符）、"aaac"（删除第四个和第五个字符）和 "aaab"（删除最后两个字符）。

Format

Input

第一行输入数据包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例数。

测试用例说明如下。

每个测试用例描述的第一行包含一个整数 $n$ ( $3 \le n \le 2 \cdot 10^5$ )。

每个测试用例说明的第二行包含一个长度为 $n$ 的字符串 $s$ ，由小写拉丁字母组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

Output

为每个测试用例打印一个整数 - 去掉两个连续字母后可得到的不同字符串的数目。

Samples

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

4
1
5
3
3
3
1

注

第一个例子在声明中已有解释。

在第三个示例中，将得到以下字符串："cdef"、"adef"、"abef"、"abcf"、"abcd"。

在第七个示例中，任何删除都将导致字符串 "aba"。

Limitation

1s, 1024KiB for each test case.