310434: CF1833A. Musical Puzzle
Description
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$.
InputThe 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'.
OutputOutput $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.
ExampleInput5 4 abab 7 abacaba 6 aaaaaa 7 abcdefg 5 babddOutput
2 4 1 6 4Note
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".
Input
题意翻译
Vlad 想要背会一段仅由 `abcdefg` 中音符构成的旋律 $s$。 但是 Vlad 只能一次性记住两个音符，如果想要记住一段旋律，就需要把记住的音符或旋律拼起来。拼起来要求前一段旋律的最后一个音符和后一段的第一个音符相同。 比如，假如 Vlad 已经记住了 `ab` 和 `ba`，那么他可以把这两段旋律拼起来，变成 `aba`（注意拼的过程中会删去那个相同的字符），然后再和 `ab` 拼成 `abab`。 Vlad 想问你，至少需要多少个这样的两个音符的旋律，才能使他记住旋律 $s$？ - 多测，数据组数不超过 $10^4$。 - $2\le|S|\le50$。Output
Vlad想在他的吉他上创作一段旋律，用字符'a', 'b', 'c', 'd', 'e', 'f', 'g'表示音符的序列。Vlad每次只能录制两个音符的旋律，他想得到旋律s，可以通过合并录制的旋律来实现。合并时，第一个旋律的最后一个音符必须与第二个旋律的第一个音符相同。要求帮助Vlad确定需要录制多少个由两个音符组成的旋律才能得到旋律s。
输入数据格式：
第一行输入一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。
接下来是每个测试用例的描述。
每个测试用例的第一行输入一个整数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
输出：
2
4
1
6
4
注意：
在第一个示例中，需要录制旋律"ab"和"ba"。
在第二个示例中，需要录制旋律"ab"、"ba"、"ac"和"ca"。
在第三个示例中，只需要录制旋律"aa"。题目大意： Vlad想在他的吉他上创作一段旋律，用字符'a', 'b', 'c', 'd', 'e', 'f', 'g'表示音符的序列。Vlad每次只能录制两个音符的旋律，他想得到旋律s，可以通过合并录制的旋律来实现。合并时，第一个旋律的最后一个音符必须与第二个旋律的第一个音符相同。要求帮助Vlad确定需要录制多少个由两个音符组成的旋律才能得到旋律s。 输入数据格式： 第一行输入一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行输入一个整数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 输出： 2 4 1 6 4 注意： 在第一个示例中，需要录制旋律"ab"和"ba"。 在第二个示例中，需要录制旋律"ab"、"ba"、"ac"和"ca"。 在第三个示例中，只需要录制旋律"aa"。