← 返回题目列表

Codeforces · 1833/A

A. 音乐拼图

中文机器翻译题面 查看原题

弗拉德决定用他的吉他创作一首旋律。让我们将旋律表示为对应于字符“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 需要录制的两个音符组成的最少旋律数。

示例

输入 #1

5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd

输出 #1

2
4
1
6
4

注意

在第一个示例中,您需要录制旋律“ab”和“ba”,如问题陈述中所述。

在第二个示例中,您需要录制旋律“ab”、“ba”、“ac”和“ca”。

在第三个样本中,唯一必要的旋律是“aa”。