题目描述

弗拉德决定用他的吉他谱写一段旋律。让我们将旋律表示为对应于字符'a', 'b', 'c', 'd', 'e', 'f', 和 ‘g' 的一系列音符。

然而，弗拉德在弹吉他方面不是很有经验，一次只能录制两个音符。弗拉德想获得旋律 $𝑠$，为此，他可以将录制的旋律合并在一起。在这种情况下，第一个旋律的最后一个音符必须与第二个旋律的第一个音符匹配。

例如，如果弗拉德录制了旋律 “ab” 和 “ba” ，他可以将它们合并在一起并得到旋律 “aba”，然后将结果与“ab” 合并得到 “abab”。

帮助弗拉德确定由两个音符组成的最小旋律数量，他需要录制以获得旋律 $s$.

输入格式

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

以下是测试用例的说明。每个测试用例的第一行包含一个整数 $𝑛 (2≤N≤50$） 表示旋律s的长度.

每个测试用例的第二行包含一个字符串𝑠长度𝑛，由字符 'a', 'b', 'c', 'd', 'e', 'f', ‘g' 组成。

输出格式

$𝑡$ 个整数，每个整数表示相应测试用例的答案。作为答案输出由弗拉德需要录制的两个音符组成最少数量的旋律。

样例

输入 #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”。