D. А и В
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$ длины $$$n$$$, состоящая только из символов '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$$$.

Вторая строка содержит строку $$$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
Примечание

В первом наборе входных данных исходная строка 'abab':

  • обменяв соседние символы на позициях $$$2$$$ и $$$3$$$, получаем строку 'aabb';
  • или обменяв символы на позициях $$$1$$$ и $$$2$$$, получаем строку 'baab'.
В обеих ситуациях выполняется ровно одна операция, после которой все буквы одного вида образуют единый блок, поэтому минимальное число операций равно $$$1$$$.

В пятом наборе входных данных строка состоит из одного символа 'b'. Единственный символ уже образует непрерывный блок, перестановки не требуются, поэтому минимальное число операций равно $$$0$$$.