CF1833A.Musical Puzzle

Vlad decided to compose a melody on his guitar. Let's represent the melody as a sequence of notes corresponding to the characters 'a', 'b', 'c', 'd', 'e', 'f', and 'g'.

However, Vlad is not very experienced in playing the guitar and can only record exactly two notes at a time. Vlad wants to obtain the melody $s$, and to do this, he can merge the recorded melodies together. In this case, the last sound of the first melody must match the first sound of the second melody.

For example, if Vlad recorded the melodies "ab" and "ba", he can merge them together and obtain the melody "aba", and then merge the result with "ab" to get "abab".

Help Vlad determine the minimum number of melodies consisting of two notes that he needs to record in order to obtain the melody $s$.

弗拉德决定用吉他创作一段旋律。我们用字符 'a'、'b'、'c'、'd'、'e'、'f' 和 'g' 组成的音符序列来表示这段旋律。

然而，弗拉德演奏吉他的经验尚浅，每次只能精确地录制两个音符。弗拉德希望得到目标旋律 $s$，为此他可以将已录制的旋律片段合并。合并时，第一个旋律的最后一个音符必须与第二个旋律的第一个音符相同。

例如，若弗拉德录制了旋律 "ab" 和 "ba"，他可将它们合并得到旋律 "aba"；再将 "aba" 与 "ab" 合并，便可得到 "abab"。

请帮助弗拉德确定：为得到旋律 $s$，他至少需要录制多少段由两个音符组成的旋律？

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

Following that are the descriptions of the test cases.

The first line of each test case contains an integer $n$ ($2 \le n \le 50$) — the length of the melody $s$.

The second line of each test case contains a string $s$ of length $n$, consisting of characters 'a', 'b', 'c', 'd', 'e', 'f', 'g'.

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

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

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 50$）—— 表示旋律字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，该字符串仅由字符 'a'、'b'、'c'、'd'、'e'、'f'、'g' 组成。

Output $t$ integers, each representing the answer for the corresponding test case. As the answer output minimum number of melodies consisting of two notes that Vlad needs to record.

输出 $t$ 个整数，每个整数表示对应测试用例的答案。答案为弗拉德需要录制的、由两个音符组成的旋律的最少数量。

In the first sample, you need to record the melodies "ab" and "ba", as described in the problem statement.

In the second sample, you need to record the melodies "ab", "ba", "ac", and "ca".

In the third sample, the only necessary melody is "aa".

在第一个样例中，你需要记录旋律 “ab” 和 “ba”，如题目描述中所述。

在第二个样例中，你需要记录旋律 “ab”、“ba”、“ac” 和 “ca”。

在第三个样例中，唯一必需的旋律是 “aa”。