← 返回题目列表

Codeforces · 1398/B

B. 子串删除游戏

中文机器翻译题面 查看原题

Alice 和 Bob 玩游戏。它们有一个二进制字符串 $$$s$$$ (一个字符串,其中的每个字符要么是 $$$0$$$ 要么是 $$$1$$$)。爱丽丝先移动,然后鲍勃,然后爱丽丝再次移动,依此类推。

在移动过程中,玩家可以选择$$$s$$$中任意数量(不少于1个)连续的相同字符并将其删除。

例如,如果字符串是$$$10110$$$,则有$$$6$$$可能的移动(删除的字符为粗体):

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

删除字符后,删除块左右的字符变得相邻。 IE。以下移动顺序有效:$$$10\textbf{11}0 \to 1\textbf{00} \to 1$$$。

当字符串变空时游戏结束,每个玩家的得分是他们删除的$$$1$$$-字符的数量。

每个玩家都想最大化自己的分数。计算爱丽丝的得分。

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 500$$$) — 测试用例的数量。

每个测试用例只包含一行,其中包含二进制字符串 $$$s$$$ ($$$1 \le |s| \le 100$$$)。

输出

对于每个测试用例,打印一个整数 - Alice 的得分结果(她删除的 $$$1$$$ 字符数)。

示例

输入 #1

5
01111001
0000
111111
101010101
011011110111

输出 #1

4
0
6
3
6

注意

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