Remove Two Letters

Description:

Input:

The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of test cases.

The descriptions of the test cases follow.

The first line of the description of each test case contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).

The second line of the description of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output:

For each test case print one integer — the number of distinct strings that can be obtained by removing two consecutive letters.

Sample Input:

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

Sample Output:

4
1
5
3
3
3
1

Note:

The first example is explained in the statement.

In the third example, the following strings are obtained: "cdef", "adef", "abef", "abcf", "abcd".

In the seventh example, any deletion will result in the string "aba".