Строка \(a=a_1a_2\dots a_n\) называется чётной, если она состоит из конкатенации (соединения) строк длины \(2\), состоящих из одинаковых символов. Иными словами, строка \(a\) четная, если одновременно выполняются два условия:
- чётна её длина \(n\);
- для всех нечётных \(i\) (\(1 \le i \le n - 1\)) выполнено \(a_i = a_{i+1}\).
Например, следующие строки являются чётными: «» (пустая строка), «tt», «aabb», «oooo» и «ttrrrroouuuuuuuukk». Следующие строки чётными не являются: «aaa», «abab» и «abba».
Задана строка \(s\), состоящая из строчных латинских букв. Необходимо найти, какое минимальное количество символов нужно удалить из строки \(s\), чтобы она стала четной. Удалённые символы не обязаны идти подряд.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное количество символов, которые необходимо удалить, чтобы строка \(s\) стала четной.
Примечание
В первом наборе входных данных можно удалить символы под номерами \(6\), \(7\) и \(9\), получив четную строку «aabbddcc».
Во втором наборе входных данных каждый символ встречается ровно один раз, поэтому для того, чтобы получить четную строку, необходимо удалить все символы из строки.
В третьем наборе входных данных можно получить четную строку «aaaabb», удалив, например, \(4\)-й и \(6\)-й символы, или строку «aabbbb», удалив \(5\)-й символ и любой из первых трех.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw
|
3
3
2
0
2
7
|