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.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    s = input()
    p = [i for i in s.split("0") if i!=""]
    p.sort(reverse=True)
    ans = 0
    for i in range(0,len(p),2):
        ans+=len(p[i])
    print(ans)



for _ in range(int(input())):
    s=[len(i)for i in input().split('0')]
    s.sort()
    print(sum(s[-1::-2]))

for _ in range(int(input())):
    s = input()
    t = [i for i in s.split("0") if i!=""]
    t.sort(reverse=True)
    cnt=0
    for i in range(0,len(t),2):
        cnt+=len(t[i])
    print(cnt)

for _ in range(int(input())):
    s = input()
    ar = []
    cur = 0
    for c in s:
        if c == "1":
            cur += 1
        else:
            ar.append(cur)
            cur = 0
    if cur != 0:
        ar.append(cur)
    ar.sort()
    ar.reverse()
    print(sum(ar[::2]))


for nt in range(int(input())):
	s = input()
	n = len(s)
	if s[0]=="1":
		count = 1
	else:
		count = 0
	groups = []
	for i in range(1,n):
		if s[i]=="1":
			count += 1
		else:
			if count:
				groups.append(count)
			count = 0
	if count:
		groups.append(count)
	groups.sort(reverse=True)
	ans = 0
	for i in range(0,len(groups),2):
		ans += groups[i]
	print (ans)


def solv():
	s=list(map(int,input()))
	v=[]
	sm=0
	for n in s:
		if n:
			sm+=1
		else:
			v.append(sm)
			sm=0
	if sm:v.append(sm)
	v.sort(reverse=True)

	res=0

	for n in range(0,len(v),2):res+=v[n]
	print(res)

for _ in range(int(input())):solv()

import math
t=int(input())
for w in range(t):
    s=sorted(input().split('0'),reverse=True)
    c=0
    for i in range(0,len(s),2):
        c+=len(s[i])
    print(c)

from itertools import groupby

t = int(input())

for _ in range(t):
    s = input()
    l = []
    for k, v in groupby(s):
        if k == '1':
            l.append(len(list(v)))
    l.sort(reverse=True)
    n = len(l)
    res = 0
    for i in range(0, n, 2):
        res += l[i]
    print(res)


for _ in range(int(input())):
    s = input()
    x = sorted(len(i) for i in s.split('0') if len(i) > 0)

    print(max(sum(x[::2]), sum(x[1::2])))

from sys import stdin,stdout
from math import sqrt,gcd,ceil,floor,log2,log10,factorial,cos,acos,tan,atan,atan2,sin,asin,radians,degrees,hypot
from bisect import insort, insort_left, insort_right, bisect_left, bisect_right, bisect
from array import array
from functools import reduce
from itertools import combinations, combinations_with_replacement, permutations
from fractions import Fraction
from random import choice,getrandbits,randint,random,randrange,shuffle
from re import compile,findall,escape
from statistics import mean,median,mode
from heapq import heapify,heappop,heappush,heappushpop,heapreplace,merge,nlargest,nsmallest

for test in range(int(stdin.readline())):
    s=input()
    l=findall(r'1+',s)
    lengths=[len(i) for i in l]
    lengths.sort(reverse=True)
    alice=0
    for i in range(0,len(lengths),2):
        alice+=lengths[i]
    print(alice)

import sys
input = sys.stdin.readline
T = int(input())

for t in range(T):
    s = input()[:-1]

    counts = []
    current = 0
    for c in s:
        if c == '1':
            current += 1
        else:
            counts.append(current)
            current = 0
    if current:
        counts.append(current)

    res = 0
    counts = sorted(counts, reverse=True)
    for i in range(len(counts)):
        if 2*i >= len(counts):
            break
        res += counts[2*i]
    print(res)


import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
	s = SI()
	a = []
	count = 0
	for i in range(len(s)):
		if s[i] == "1":
			count+=1
		else:
			a.append(count)
			count = 0
	a.append(count)
	a.sort(reverse=True)
	print(sum(a[0:len(a):2]))

from math import *
from collections import *
from random import *
from decimal import Decimal
from heapq import *
from bisect import *
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**5)
def lis():
    return list(map(int,input().split()))
def ma():
    return list(map(int,input().split()))
def inp():
    return int(input())
def st1():
    return input().rstrip('\n')
t=inp()
while(t):
    t-=1
    #n=inp()
    a=st1()
    oe=[]
    c=0
    for i in a:
        if(i=='1'):
            c+=1
        else:
            if(c!=0):
                oe.append(c)
                c=0
    if(c):
        oe.append(c)
    s=0
    oe.sort(reverse=True)
    for i in range(len(oe)):
        if(i%2==0):
            s+=oe[i]
    print(s)
        


for _ in range(int(input())):
    s = input() + '0'
    A = []
    tr = False
    x = 0
    for i in range(len(s)):
        if s[i] == '1':
            if tr:
                x += 1
            else:
                tr = True
                x = 1
        else:
            if tr:
                tr = False
                A.append(x)
    A.sort(reverse=True)
    Ans = 0
    for i in range(len(A)):
        if i % 2 == 0:
            Ans += A[i]
    print(Ans)

t = int(input())
while t:
    s = input()
    arr = []
    k = 0
    for i in s:
        if i == '1':
            k += 1
        else:
            arr.append(k)
            k = 0
    if k:
        arr.append(k)
    arr.sort(reverse=True)
    ans = 0
    for i in range(0, len(arr), 2):
        ans += arr[i]
    print(ans)
    t -= 1


import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    x = input().rstrip()
    
    arr = []
    
    c = 0
    for char in x:
        if char=='1':
            c+=1
        else:
            arr.append(c)
            c = 0
            
    arr.append(c)
    arr.sort()
    arr.reverse()
    
    ans = 0
    for i in range(0,len(arr),2):
        ans += arr[i]
        
    print(ans)

import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    S=input().strip()+"0"

    L=[]

    NOW=0
    for s in S:
        if s=="0":
            L.append(NOW)
            NOW=0
        else:
            NOW+=1

    L.sort(reverse=True)

    ANS=0

    for i in range(0,len(L),2):
        ANS+=L[i]

    print(ANS)
        


for _ in range (int(input())):
    s=input()
    a = []
    flag = 0
    count = 0
    for i in range (len(s)):
        if s[i]=='1':
            count+=1
        else:
            a.append(count)
            count=0
        if i==len(s)-1 and count!=0:
            a.append(count)
    a.sort(reverse=True)
    ans = 0
    for i in range(len(a)):
        if i%2==0:
            ans+=a[i]
    print(ans)

for t in range(int(input())):
	s = input()
	last = -1
	num = []
	n = len(s)
	for i in range(n):
		if (s[i] == "0"):
			if (i - last - 1 > 0):
				num.append(i - last - 1)
			last = i
	if (n - last - 1 > 0):
		num.append(n - last - 1)
	num = sorted(num)[::-1]
	ans = 0
	for i in range(0, len(num), 2):
		ans += num[i]
	print(ans)

for test in range(int(input())):
    s = input()
    a = []
    now = 0
    n = len(s)
    for i in range(n):
        if s[i] == "0":
            if now > 0:
                a.append(now)
            now = 0
        else:
            now += 1
    if now > 0:
        a.append(now)
    a.sort(reverse=True)
    ans = 0
    for i in range(0, len(a), 2):
        ans += a[i]
    print(ans)

for _ in range(int(input())):
    s = input()

    ones = []
    cnt = 0
    for i in s:
        if i == '1':
            cnt += 1
        else:
            if cnt != 0:
                ones.append(cnt)
                cnt = 0
    if cnt != 0:
        ones.append(cnt)

    ones.sort(reverse=True)
    print(sum(ones[::2]))


from collections import defaultdict as dd
import math
import sys
input=sys.stdin.readline
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))

def solve():
	s = input()

	sets = []
	streak = 0
	for i in range(len(s)):
		if s[i]=='1':
			streak+=1
		else:
			if streak>0:
				sets.append(streak)
				streak=0
	if streak>0:
		sets.append(streak)
		streak=0

	sets.sort(reverse=True)

	print(sum(sets[::2]))


q=nn()
for _ in range(q):
	solve()


t = int(input())

for _ in range(t):
    s = [int(i) for i in input().strip()]
    n = len(s)
    bckt = []
    ct = 0
    
    for i in range(n):
        if s[i]:
            ct += 1
        else:
            if ct:
                bckt.append(ct)
                ct = 0
    
    if ct:
        bckt.append(ct)
        
    bckt.sort(reverse=True)
    print(sum(bckt[::2]))

for i in range(int(input())):
	ip=list(map(int,input()))
	ones=[]
	tot=0
	for i in ip:
		if i==1:
			tot+=1
		else:
			ones.append(tot)
			tot=0
	if tot:ones.append(tot)
	ones.sort(reverse=True)
	ans=0
	for i in range(0,len(ones),2):
		ans+=ones[i]
	print(ans)

#BINOD
import math
test = int(input())
for t in range(test):
    s = input()
    n = len(s)
    A = []
    o=0
    for i in range(n):
        if(s[i]=='1'):
            o+=1
        else:
            A.append(o)
            o=0
    if(s[n-1]=='1'):
        A.append(o)
    A.sort(reverse = True)
    ans = 0
    for i in range(0,len(A),2):
        ans += A[i]
    print(ans)




#Binod


for _ in range(int(input())):
    data = list(map(int,list(input())))
    fl = False
    data.append("&")
    l = 0
    st = []
    for i in range(len(data)):
        if fl and data[i] == 1:
            l+=1
            continue
        if fl and data[i]!=1:
            st.append(l)
            l = 0
            fl = False
            continue
        if not fl and data[i] == 1:
            l = 1
            fl = True
    st.sort(reverse=True)
    c1 = 0
    for i in range(0,len(st),2):
        c1+=st[i]
    print(c1)

import math
from collections import deque
from sys import stdin, stdout
from string import ascii_letters
input = stdin.readline
#print = stdout.write
letters = ascii_letters[:26]
 
for _ in range(int(input())):
    arr = list(map(int, input().strip()))
    lens = []
    count = 0
    for i in arr:
        if i == 0:
            if count > 0:
                lens.append(count)
            count = 0
        else:
            count += 1
    if count > 0:
        lens.append(count)
    lens.sort(reverse=True)
    res = 0
    for i in range(0, len(lens), 2):
        res += lens[i]
    print(res)