CF1800D.Remove Two Letters

Dmitry has a string $s$, consisting of lowercase Latin letters.

Dmitry decided to remove two consecutive characters from the string $s$ and you are wondering how many different strings can be obtained after such an operation.

For example, Dmitry has a string "aaabcc". You can get the following different strings: "abcc"(by deleting the first two or second and third characters), "aacc"(by deleting the third and fourth characters),"aaac"(by deleting the fourth and the fifth character) and "aaab" (by deleting the last two).

德米特里有一个由小写拉丁字母组成的字符串 $s$。

德米特里决定从字符串 $s$ 中删除两个连续的字符，你希望知道通过这种操作能得到多少种不同的字符串。

例如，德米特里的字符串为 "aaabcc"。通过删除两个连续字符，可以得到以下几种不同的字符串："abcc"（删除前两个字符，或删除第二和第三个字符）、"aacc"（删除第三和第四个字符）、"aaac"（删除第四和第五个字符）以及 "aaab"（删除最后两个字符）。

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

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

随后是各测试用例的描述。

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

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

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

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

对于每个测试用例，输出一个整数——即通过删除两个相邻字母所能得到的不同字符串的数量。

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".

第一个示例在题目描述中已作解释。

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

在第七个示例中，任意一次删除操作都会得到字符串 "aba"。