题目描述

Vlad 决定用吉他创作一段旋律。我们可以将这段旋律表示为由字符 'a'、'b'、'c'、'd'、'e'、'f' 和 'g' 组成的音符序列。

然而，Vlad 在弹吉他方面经验尚浅，每次只能准确地录制两个音符。Vlad 想要得到旋律 $s$，为此他可以将录制好的旋律片段合并起来。在合并时，第一个旋律片段的最后一个音符必须与第二个旋律片段的第一个音符相同。

例如，如果 Vlad 录制了旋律 "ab" 和 "ba"，他可以将它们合并得到 "aba"，然后再与 "ab" 合并得到 "abab"。

请你帮助 Vlad 确定，为了得到旋律 $s$，他最少需要录制多少个由两个音符组成的旋律片段。

输入格式

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

接下来是每个测试用例的描述。

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

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

输出格式

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

说明/提示

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

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

在第三个样例中，唯一需要的旋律片段是 "aa"。

由 ChatGPT 4.1 翻译

样例

5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd

2
4
1
6
4