题目描述

江月诗有一个长度为 $n$ 的字符串 $s$，仅由字符 $\rm a$ 和 字符 $\rm b$ 组成，江月诗认为字符（$\rm a$ 或 $\rm b$）全部连续地排列在一起，形成恰好一个连续的 $\rm ab$ 块的字符串就是一个 好串$^{\dagger}$。

现在你可以进行多次操作，每次操作，你可以选择一个位置 $i$（$1 \le i \le n-1$），交换相邻的字符 $s_i$ 和 $s_{i+1}$。

你需要用最少的操作次数，让最终的字符串变为 好串$^{\dagger}$。

注意：另一种字符可以在这个块的前面或后面，形成最多两个（可能为空）的块。

$^{\dagger}$ 以下是一些好串的最终形式示例：

• $\rm aaabbbaaa$ —— 所有的 $\rm b$ 连续在一起（一个块），$\rm a$ 可以在这个块前后；
• $\rm bbbaaaaaabbb$ —— 所有的 $\rm a$ 连续在一起，$\rm b$ 则在字符串边缘；
• $\rm aaaaabbbb$ 或 $\rm bbbbaaaaa$ —— 两种字符分别各自形成一个连续块。

你需要计算，实现上述目标状态所需的最小操作次数。

输入格式

输入包含若干组测试数据。

第一行输入一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的组数。

每组测试数据第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示字符串 $s$ 的长度。

第二行输入一个仅包含字符 $\rm a$ 和 $\rm b$，长度为 $n$ 的字符串 $s$。

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

输出格式

对于每组测试数据，输出一行一个整数，表示使同一种字符形成一个连续块所需的最小操作次数。

输入输出样例 #1

输入 #1

5
4
abab
6
bababa
7
abababa
2
ab
1
b

输出 #1

1
2
2
0
0

说明/提示

在第一个测试用例中，初始字符串为 $\rm abab$：

• 交换相邻的第 $2$ 和 $3$ 个字符后，得到字符串 $\rm aabb$；
• 或交换第 $1$ 和 $2$ 个字符后，得到字符串 $\rm baab$。

两种情况下都只需操作一次，之后同一类字符已经连在一起，故最少操作次数为 $1$。

在第五个测试用例中，字符串仅包含一个字符 $\rm b$。单个字符已经形成了连续块，不需要任何操作，输出 $0$。