ACM-ICPC-OJ训练营

问题 D: 音乐拼图(思维)

时间限制: 1 Sec 内存限制: 256 MB
提交: 0 解决: 2
[提交][状态][讨论版][命题人:]

题目描述

弗拉德决定用他的吉他谱写一段旋律。让我们把这段旋律表示为一连串的音符，对应于'a'、'b'、'c'、'd'、'e'、'f'、'g'等字符。
然而，Vlad在弹奏吉他方面经验不足，每次只能准确记录两个音符。Vlad想获得旋律s，要做到这一点，他可以把录制的旋律合并在一起。在这种情况下，第一个旋律的最后一个音必须与第二个旋律的第一个音相匹配。
例如，如果Vlad记录了旋律 "ab "和 "ba"，他可以把它们合并在一起，得到旋律 "aba"，然后把这个结果与 "ab "合并，得到 "abab"。
帮助Vlad确定他需要记录的由两个音符组成的最小数量的旋律，以获得旋律s。

输入描述

第一行输入包含一个整数t（1≤t≤10⁴)--测试用例的数量。之后是测试用例的描述。
每个测试用例的第一行包含一个整数n（2≤n≤50）--旋律的长度s.
每个测试用例的第二行包含一个长度为n的字符串s，由字符'a', 'b', 'c', 'd', 'e', 'f', 'g'组成。

输出描述

输出t个整数，每个整数代表相应测试案例的答案。作为答案，输出Vlad需要记录的由两个音符组成的最小数量的旋律。

样例输入

5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd

样例输出

提示

在第一个样本中，你需要记录 "ab "和 "ba "的旋律，如问题陈述中所述。

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

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

[提交][状态]