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

У Дмитрия есть строка $$$s$$$, состоящая из строчных латинских букв.

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

Например, у Дмитрия есть строка «aaabcc». Вы можете получить следующие различные строки: «abcc»(при удалении первых двух или второго и третьего символов), «aacc»(при удалении третьего и четвёртого символов),«aaac»(при удалении четвертого и пятого символов) и «aaab»(при удалении последних двух).

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

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

Далее следуют описания входных данных.

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

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

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

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

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

Пример
Входные данные
7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa
Выходные данные
4
1
5
3
3
3
1
Примечание

Первый пример разобран в условии.

В третьем примере получатся следующие строки: «cdef», «adef», «abef», «abcf», «abcd».

В седьмом примере при любом удалении получится строка «aba».