给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 'a' 和 'b'.
在一次操作中,您可以选择一个位置 $$$i$$$ ($$$1 \le i \le n-1$$$) 并交换相邻字符 $$$s_i$$$ 和 $$$s_{i+1}$$$。
您需要执行最少数量的操作,以确保一种类型的所有字符($$$a$$$ 或 $$$b$$$)严格位于在一起,形成一个连续的块。
另一种类型的字符可以放置在该块之前或之后,形成两个(可能是空的)块。
有效最终表格示例:
- 'aaabbbaaa' — 全部 'b位于一起(一个块),'a可以在此块之前或之后;
- 'bbbaaaaaabbb' — 全部 'a在一起,'b位于字符串的边缘;
- 'aaaaabbbb' 或 'bbbbaaaaa' — 两种类型的字符各形成一个连续块。
您需要找到实现指定状态所需的最少描述操作数。
输入
每个测试由多个测试用例组成。
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 'a' 和 'b'.
保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——两种类型之一的所有字符形成单个连续块所需的最小操作数。
示例
输入复制
54abab6bababa7abababa2ab1b
输出复制
12200
注意
在第一个测试用例中,初始字符串是 'abab':
- 通过交换位置 $$$2$$$ 和 $$$3$$$ 处的相邻字符,我们得到字符串 'aabb';
- 或者通过交换位置 $$$1$$$ 和 $$$2$$$ 处的字符,我们得到字符串 '咩咩'.
在第五个输入测试用例中,字符串由单个字符 ' 组成b'。单个字符已经形成一个连续的块,不需要交换,所以最少的操作次数是$$$0$$$。