Dmitry 有一个由小写拉丁字母组成的字符串 s。

他决定从 s 中**删除两个连续的字符**（删除的位置可以任意选择）。问：一共能得到多少种**互不相同**的字符串？

例如 s= `aaabcc`：删第 1~2 个或第 2~3 个字符都得到 `abcc`；删第 3~4 个得 `aacc`；删第 4~5 个得 `aaac`；删第 5~6 个得 `aaab`。共 4 种。

第一行一个整数 t，表示数据组数。

接下来每组两行：第一行整数 n，第二行长度为 n 的字符串 s（仅含小写字母）。

每组输出一行一个整数，表示能得到的不同字符串数量。

样例 1 :

`aaaaaaaaaa` 怎么删都得到 8 个 a，共 1 种；

`abcdef` 删 5 个不同位置得到 5 种；

`ababa` 任何删除都得到 `aba`，共 1 种。

样例 2：`aacaa` 删法得到 `caa`（删 1~2）、`aaa`（删 2~3 或 3~4）、`aac`（删 4~5），共 3 种。

| 20% | 1~5 | 20 | n \le 20 | 

| 60% | 6~15 | 40（累计 60） | n \le 2000 | 

| 100% | 16~25 | 40（累计 100） | n \le 2 \times 10^5，t 组合计 n \le 2\times 10^5 |