Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Влад нашёл строку $$$s$$$ из $$$n$$$ строчных латинских букв, и он хочет сделать её как можно короче.

Для этого он может любое число раз удалять из $$$s$$$ любые два соседних символа, если они различны. Например, если $$$s$$$=racoon, то удалив одну пару символов, он может получить строку coon, roon, raon и raco, но не может получить racn (потому что удалённые буквы были одинаковы) или rcon (потому что удалённые буквы не были соседними).

Какой минимальной длины может добиться Влад, применив любое число удалений?

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

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

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

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

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

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

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

Пример
Входные данные
10
4
aabc
5
abaca
10
avbvvcvvvd
7
abcdefg
5
dabbb
8
aacebeaa
7
bbbbacc
6
dacfcc
6
fdfcdc
9
dbdcfbbdc
Выходные данные
0
1
2
1
1
0
1
0
0
1
Примечание

В первом наборе выходных данных примера нужно действовать следующим образом «aabc» $$$\rightarrow$$$ «ac» $$$\rightarrow$$$ «». Обратите внимание, что при другом порядке удалений строка не станет пустой.