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

Алиса и Боб играют в игру. У них есть бинарная строка $$$s$$$ (каждый символ бинарной строки — либо $$$0$$$, либо $$$1$$$). Алиса ходит первой, потом Боб, потом снова Алиса, и так далее.

В свой ход игрок должен выбрать несколько (не менее одного) последовательных одинаковых символов в $$$s$$$ и удалить их.

Например, если текущая строка — $$$10110$$$, существует $$$6$$$ возможных ходов (удаляемые символы выделены жирным):

  1. $$$\textbf{1}0110 \to 0110$$$;
  2. $$$1\textbf{0}110 \to 1110$$$;
  3. $$$10\textbf{1}10 \to 1010$$$;
  4. $$$101\textbf{1}0 \to 1010$$$;
  5. $$$10\textbf{11}0 \to 100$$$;
  6. $$$1011\textbf{0} \to 1011$$$.

После удаления символов те символы, которые стояли слева и справа от удаленного блока, становятся последовательными. Т. е. следующая последовательность операций возможна: $$$10\textbf{11}0 \to 1\textbf{00} \to 1$$$.

Игра заканчивается, когда строка становится пустой. Счет каждого игрока равен кол-ву символов $$$1$$$, которые он удалил.

Каждый игрок хочет набрать максимально возможное количество очков. Посчитайте, сколько очков наберет Алиса.

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

В первой строке задано одно целое число $$$T$$$ ($$$1 \le T \le 500$$$) — количество наборов входных данных.

Каждый набор входных данных содержит одну бинарную строку $$$s$$$ ($$$1 \le |s| \le 100$$$).

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

Для каждого набора входных данных выведите ответ на него — счет Алисы в конце игры (количество символов $$$1$$$, которые она удалит).

Пример
Входные данные
5
01111001
0000
111111
101010101
011011110111
Выходные данные
4
0
6
3
6
Примечание

Вопросы по поводу оптимальной стратегии будут игнорироваться.