E. 交替字符串

每个测试的时间限制：2 秒
内存限制：256 兆字节

题目描述

樱子非常喜欢交替字符串。如果一个由小写拉丁字母组成的字符串 $s$ 满足以下条件，她称其为交替字符串：

• 所有偶数位置上的字符相同
• 所有奇数位置上的字符相同
• 字符串长度为偶数

例如，字符串 "abab" 和 "gg" 是交替字符串，而 "aba" 和 "ggwp" 不是。

作为好朋友，你决定送给她这样一个字符串，但你找不到。幸运的是，你可以对字符串执行两种类型的操作：

1. 删除操作：选择一个下标 $i$，删除字符串中的第 $i$ 个字符，这将使字符串长度减少 $1$。这种操作最多只能执行 $1$ 次；
2. 替换操作：选择一个下标 $i$，将 $s_i$ 替换为任意其他字母。

由于你很着急，你需要确定使字符串成为交替字符串所需的最少操作次数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）—— 字符串的长度。

每个测试用例的第二行包含一个字符串 $s$，由小写拉丁字母组成。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 将字符串 $s$ 转换为交替字符串所需的最少操作次数。

输入样例

10
1
a
2
ca
3
aab
5
ababa
6
acdada
9
ejibmyyju
6
bbccbc
6
abacba
5
bcbca
5
dcbdb

输出样例

1
0
1
1
2
6
2
3
1
1

样例解释

• 对于字符串 "ababa"，你可以删除第一个字符得到 "baba"，这是一个交替字符串。
• 对于字符串 "acdada"，你可以修改前两个字符得到 "dadada"，这是一个交替字符串。