human
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):

  1. 10110 → 0110.

  2. 10110 → 1110.

  3. 10110 → 1010.

  4. 10110 → 1010.

  5. 10110 → 100.

  6. 10110 → 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: 10110 → 100 → 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 ≤ T ≤ 500) — the number of test cases.

Each test case contains exactly one line containing a binary string s (1 ≤ |s| ≤ 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.
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python code to print one integer — the resulting score of Alice (the number of 1-characters deleted by her).

from functools import reduce

def get_indices_of(b_str,ch):
  length = len(b_str)

  def get_indices(idx,idx_lst):
    if(idx == length):
      return idx_lst
    else:
      if(b_str[idx] == ch):
        idx_lst.append(idx)
        return get_indices((idx+1),idx_lst)
      else:
        return get_indices((idx+1),idx_lst)

  return get_indices(0,[])

def get_indices_of_1(b_str):
  return get_indices_of(b_str,'1')

def calculate_score(indices_lst):
  
  def add_score(score,idx):
    [scores,prevIdx] = score
    if(prevIdx == -1):
      scores.append(1)
      return [scores,idx]
    if((prevIdx + 1) == idx):
      scores[-1] += 1
      return [scores,idx]
    else:
      scores.append(1)
      return [scores,idx]
    
  return reduce(lambda score,idx: add_score(score,idx),indices_lst,[[],-1])

def even(x):
  return x % 2 == 0

def compute_total_score(scores):
  length = len(scores)  

  def score(scores,idx,player):
    if(length == idx):
      return player[0]
    else:
      if(even(idx)):
        player[0] += scores[idx]
      else:
        player[1] += scores[idx]
      return score(scores,(idx+1),player)

  return score(scores,0,[0,0])

def main():
  test_case = int(input())
  for i in range(test_case):
    b_str = input()
    scores = (calculate_score(get_indices_of_1(b_str)))[0]
    scores.sort(reverse=True)
    print(compute_total_score(scores))

main()