#1387. C-小梦的AB交换
C-小梦的AB交换
题目描述
小梦有一个长度为 的 串 ,即 中只包含 "" 和 "" 两种字符,且其中恰好有 个 "" 和 个 ""。
他可以对 执行以下操作:
选择 ,并交换 和 。
他想知道,需要至少多少次操作,才能使得 满足相邻的字符不相同,请你帮他算一算吧。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 ,表示数据组数。
接下来包含 组数据,每组数据的格式如下:
第一行一个正整数 ,表示 长度的一半。
第二行一个长度为 的字符串 ,保证只由 "", "" 两种字符构成。
输出格式
对于每组测试数据:
在单独的一行输出一个整数,表示最少进行的操作次数。
样例
2
3
AAABBB
3
ABAABB
1
1
题目来源:洛谷 U535982