← 返回题目列表

Codeforces · 2008/E

E. 交替字符串

中文机器翻译题面 查看原题

樱子真的很喜欢交替的弦。如果偶数位置的字符相同,奇数位置的字符相同,并且字符串的长度为偶数,则她将小写拉丁字母 $$$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\cdot 10^5$$$) — 字符串的长度。

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

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

输出

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

示例

输入 #1

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

输出 #1

1
0
1
1
2
6
2
3
1
1

注意

对于字符串ababa,可以删除第一个字符得到baba,这是一个交替字符串。

对于字符串acdada,您可以更改前两个字符以获得dadada,这是一个交替字符串。