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
注意
关于最优策略的问题将被忽略。