弗拉德决定用他的吉他创作一首旋律。让我们将旋律表示为对应于字符“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”。