题目描述

给定一个长度为 $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$）——测试用例数。随后为 $t$ 个测试用例。

每个测试用例包含两行：

• 第一行：整数 $n$（$1\le n\le 2\cdot 10^5$），表示字符串长度。
• 第二行：字符串 $s$，长度为 $n$，仅包含字符 'a' 和 'b'。

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

输出格式

对每个测试用例输出一行，包含一个整数 —— 使其中一种字符形成一个连续块所需的最少交换次数。

样例输入

5
4
abab
6
bababa
7
abababa
2
ab
1
b

样例输出

1
2
2
0
0

说明

样例解释

样例 $1$：初始字符串 abab，交换位置 $2$ 和 $3$（得到 aabb），或交换位置 $1$ 和 $2$（得到 baab）均可在 $1$ 次操作内使某一字符成块，因此最少为 $1$。

样例 $5$：字符串只有一个字符 b，已满足条件，所需操作为 $0$。