题目描述

Alice 和 Bob 玩一个游戏。他们有一个二进制字符串 $s$（即字符串中的每个字符都是 $0$ 或 $1$）。Alice 先手，然后是 Bob，然后再次轮到 Alice，如此交替进行。

在每一次操作中，玩家可以选择 $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$ 字符的数量。

每位玩家都希望最大化自己的得分。请计算 Alice 的最终得分。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 500$），表示测试用例的数量。

每个测试用例包含一行，仅包含一个二进制字符串 $s$（$1 \le |s| \le 100$）。

输出格式

对于每个测试用例，输出一个整数，表示 Alice 的最终得分（即她删除的 $1$ 字符的数量）。

说明/提示

关于最优策略的问题将被忽略。

由 ChatGPT 4.1 翻译

样例

5
01111001
0000
111111
101010101
011011110111

4
0
6
3
6