#1387. C-小梦的AB交换

C-小梦的AB交换

题目描述

小梦有一个长度为 2∗n2 * n 的 ABAB 串 ss,即 ss 中只包含 "AA" 和 "BB" 两种字符,且其中恰好有 nn 个 "AA" 和 nn 个 "BB"。

他可以对 ss 执行以下操作:

∙\bullet 选择 i,j (1≤i,j≤2⋅n,i≠j)i, j\ (1 \leq i, j \leq 2\cdot n, i \ne j),并交换 sis_i 和 sjs_j。

他想知道,需要至少多少次操作,才能使得 ss 满足相邻的字符不相同,请你帮他算一算吧。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 TT,表示数据组数。

接下来包含 TT 组数据,每组数据的格式如下:

第一行一个正整数 nn,表示 ss 长度的一半。

第二行一个长度为 2∗n2*n 的字符串 ss,保证只由 "AA", "BB" 两种字符构成。

输出格式

对于每组测试数据:

在单独的一行输出一个整数,表示最少进行的操作次数。

样例

2
3
AAABBB
3
ABAABB
1
1

题目来源:洛谷 U535982