Влад нашёл строку \(s\) из \(n\) строчных латинских букв, и он хочет сделать её как можно короче.
Для этого он может любое число раз удалять из \(s\) любые два соседних символа, если они различны. Например, если \(s\)=racoon, то удалив одну пару символов, он может получить строку coon, roon, raon и raco, но не может получить racn (потому что удалённые буквы были одинаковы) или rcon (потому что удалённые буквы не были соседними).
Какой минимальной длины может добиться Влад, применив любое число удалений?
Выходные данные
Для каждого набора выведите единственное число — минимальную длину строки \(s\), после удаления пар соседних символов, значения которых различны.
Примечание
В первом наборе выходных данных примера нужно действовать следующим образом «aabc» \(\rightarrow\) «ac» \(\rightarrow\) «». Обратите внимание, что при другом порядке удалений строка не станет пустой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|