Alice and Bob play a game. They have a binary string $s$ (a string such that each character in it is either $0$ or $1$). Alice moves first, then Bob, then Alice again, and so on.

During their move, the player can choose any number (not less than one) of consecutive equal characters in $s$ and delete them.

For example, if the string is $10110$, there are $6$ possible moves (deleted characters are bold):  $\textbf{1}0110 \to 0110$;  $1\textbf{0}110 \to 1110$;  $10\textbf{1}10 \to 1010$;  $101\textbf{1}0 \to 1010$;  $10\textbf{11}0 \to 100$;  $1011\textbf{0} \to 1011$. 

After the characters are removed, the characters to the left and to the right of the removed block become adjacent. I. e. the following sequence of moves is valid: $10\textbf{11}0 \to 1\textbf{00} \to 1$.

The game ends when the string becomes empty, and the score of each player is the number of $1$-characters deleted by them.

Each player wants to maximize their score. Calculate the resulting score of Alice.


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 500$) — the number of test cases.

Each test case contains exactly one line containing a binary string $s$ ($1 \le |s| \le 100$).


-----Output-----

For each test case, print one integer — the resulting score of Alice (the number of $1$-characters deleted by her).


-----Example-----
Input
5
01111001
0000
111111
101010101
011011110111

Output
4
0
6
3
6



-----Note-----

Questions about the optimal strategy will be ignored.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from math import *\nfrom collections import *\nfrom random import *\nfrom decimal import Decimal\nfrom heapq import *\nfrom bisect import *\nimport sys\ninput=sys.stdin.readline\nsys.setrecursionlimit(10**5)\ndef lis():\n    return list(map(int,input().split()))\ndef ma():\n    return list(map(int,input().split()))\ndef inp():\n    return int(input())\ndef st1():\n    return input().rstrip('\\n')\nt=inp()\nwhile(t):\n    t-=1\n    #n=inp()\n    a=st1()\n    oe=[]\n    c=0\n    for i in a:\n        if(i=='1'):\n            c+=1\n        else:\n            if(c!=0):\n                oe.append(c)\n                c=0\n    if(c):\n        oe.append(c)\n    s=0\n    oe.sort(reverse=True)\n    for i in range(len(oe)):\n        if(i%2==0):\n            s+=oe[i]\n    print(s)\n        \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 21225