Строка $$$a=a_1a_2\dots a_n$$$ называется чётной, если она состоит из конкатенации (соединения) строк длины $$$2$$$, состоящих из одинаковых символов. Иными словами, строка $$$a$$$ четная, если одновременно выполняются два условия:
Например, следующие строки являются чётными: «» (пустая строка), «tt», «aabb», «oooo» и «ttrrrroouuuuuuuukk». Следующие строки чётными не являются: «aaa», «abab» и «abba».
Задана строка $$$s$$$, состоящая из строчных латинских букв. Необходимо найти, какое минимальное количество символов нужно удалить из строки $$$s$$$, чтобы она стала четной. Удалённые символы не обязаны идти подряд.
В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.
Далее следуют описания наборов входных данных.
Каждый набор входных данных состоит из одной строки $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), где $$$|s|$$$ — длина строки $$$s$$$. Строка состоит из строчных букв латинского алфавита.
Гарантируется, что сумма $$$|s|$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите единственное число — минимальное количество символов, которые необходимо удалить, чтобы строка $$$s$$$ стала четной.
6 aabbdabdccc zyx aaababbb aabbcc oaoaaaoo bmefbmuyw
3 3 2 0 2 7
В первом наборе входных данных можно удалить символы под номерами $$$6$$$, $$$7$$$ и $$$9$$$, получив четную строку «aabbddcc».
Во втором наборе входных данных каждый символ встречается ровно один раз, поэтому для того, чтобы получить четную строку, необходимо удалить все символы из строки.
В третьем наборе входных данных можно получить четную строку «aaaabb», удалив, например, $$$4$$$-й и $$$6$$$-й символы, или строку «aabbbb», удалив $$$5$$$-й символ и любой из первых трех.
| Codeforces Round 780 (Div. 3) |
|---|
| Закончено |
