E. Чередующаяся строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сакурако очень любит чередующиеся строки. Она называет строку $$$s$$$ из строчных латинских букв чередующейся строкой, если символы на четных позициях одинаковы, если символы на нечетных позициях одинаковы и длина строки четная.

Например, строки 'abab' и 'gg' являются чередующимися, а строки 'aba' и 'ggwp' — нет.

Как хороший друг, вы решили подарить такую строку, но не смогли её найти. К счастью, вы можете выполнить два типа операций над строкой:

  1. Выберите индекс $$$i$$$ и удалите из строки $$$i$$$-й символ, что уменьшит длину строки на $$$1$$$. Такую операцию можно выполнить не более $$$1$$$ раза;
  2. Выберите индекс $$$i$$$ и замените $$$s_i$$$ на любую другую букву.

Поскольку вы торопитесь, вам нужно определить минимальное количество операций, необходимых для превращения строки в чередующуюся.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$)  — количество наборов входных данных.

Первая строка каждого набора содержит одно число $$$n$$$ ($$$1 \le n\le 2\cdot 10^5$$$)  — длина строки.

Вторая строка каждого набора содержит строку $$$s$$$, состоящую из строчных латинских букв.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого тестового случая выведите одно целое число — минимальное количество операций, необходимых для превращения строки $$$s$$$ в чередующуюся.

Пример
Входные данные
10
1
a
2
ca
3
aab
5
ababa
6
acdada
9
ejibmyyju
6
bbccbc
6
abacba
5
bcbca
5
dcbdb
Выходные данные
1
0
1
1
2
6
2
3
1
1
Примечание

Для строки ababa можно удалить первый символ, чтобы получить baba, что является чередующейся строкой.

Для строки acdada можно изменить первые два символа, чтобы получить dadada, что является чередующейся строкой.