#include <bits/stdc++.h>
using namespace std;
void show(vector<long long> &v) {
  for (long long i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
  }
  cout << "\n";
}
bool isin(int i, int j, int x, int y) {
  return (i < x) && (i >= 0) && (j < y) && (j >= 0);
}
long long power(long long a, long long b, long long p) {
  long long res = 1;
  a = a % p;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % p;
    }
    b /= 2;
    a = (a * a) % p;
  }
  return res;
}
bool check(vector<long long> &a, long long samecnt, long long sz) {
  long long taken = 0;
  for (long long i = a.size() - 1; i >= 0; i--) {
    taken += a[i] / samecnt;
  }
  return (taken >= sz);
}
long long fib(long long n) {
  double phi = (1.0 + sqrt(5)) / 2.0;
  double res = (powl(phi, n) - powl(-phi, -n)) / sqrt(5);
  return (long long)floor(res);
}
long long count(long long total, long long running, long long a) {
  long long for_a, midcnt, right, rem;
  long long tot_sum = (total) * (running) - (((running) * (running + 1)) / 2);
  long long left = (total - 1) % a, lval = 0, rval = 0, midval = 0;
  rem = max(running - (left + 1), 0LL);
  midcnt = rem / a;
  right = rem % a;
  rval = (right)*a - (((right) * (right + 1)) / 2);
  lval = (((left) * (left + 1)) / 2);
  midval = midcnt * (((a) * (a - 1)) / 2);
  for_a = tot_sum - (lval + midval + rval);
  for_a /= a;
  for_a += running;
  return for_a;
}
pair<long long, pair<long long, long long> > dfs(
    vector<vector<long long> > &adj, long long curr, vector<long long> &vis,
    long long total, long long running, long long a, long long b, long long lcm,
    vector<long long> &va, vector<long long> &vb, vector<long long> &vl) {
  vis[curr] = 1;
  pair<long long, pair<long long, long long> > sum = {0, {0, 0}};
  bool isleaf = true;
  for (long long i = 0; i < adj[curr].size(); i++) {
    if (i == 0) {
      pair<long long, pair<long long, long long> > temp;
      temp = dfs(adj, adj[curr][i], vis, total + 1, running + 1, a, b, lcm, va,
                 vb, vl);
      sum.first += temp.first;
      sum.second.first += temp.second.first;
      sum.second.second += temp.second.second;
    } else {
      pair<long long, pair<long long, long long> > temp;
      temp = dfs(adj, adj[curr][i], vis, total + 1, 1, a, b, lcm, va, vb, vl);
      sum.first += temp.first;
      sum.second.first += temp.second.first;
      sum.second.second += temp.second.second;
    }
    isleaf = false;
  }
  if (isleaf) {
    long long for_a = count(total, running, a);
    long long for_b = count(total, running, b);
    long long for_lcm = count(total, running, lcm);
    sum = {for_lcm, {for_a, for_b}};
  }
  va[curr] = sum.second.first;
  vb[curr] = sum.second.second;
  vl[curr] = sum.first;
  return sum;
}
void solve() {
  string s;
  cin >> s;
  vector<long long> num;
  char pre = '0';
  long long cnt = 0;
  for (long long i = 0; i < s.size(); ++i) {
    if (s[i] == '0') {
      if (cnt > 0) {
        num.push_back(cnt);
        cnt = 0;
      }
    } else {
      cnt++;
    }
  }
  if (cnt > 0) {
    num.push_back(cnt);
    cnt = 0;
  }
  sort(num.rbegin(), num.rend());
  long long alice = 0;
  for (long long i = 0; i < num.size(); ++i) {
    if (i % 2 == 0) {
      alice += num[i];
    }
  }
  cout << alice << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  int t;
  cin >> t;
  for (long long t1 = 0; t1 < t; ++t1) {
    solve();
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void show(vector<long long> &v) {
  for (long long i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
  }
  cout << "\n";
}
bool isin(int i, int j, int x, int y) {
  return (i < x) && (i >= 0) && (j < y) && (j >= 0);
}
long long power(long long a, long long b, long long p) {
  long long res = 1;
  a = a % p;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % p;
    }
    b /= 2;
    a = (a * a) % p;
  }
  return res;
}
bool check(vector<long long> &a, long long samecnt, long long sz) {
  long long taken = 0;
  for (long long i = a.size() - 1; i >= 0; i--) {
    taken += a[i] / samecnt;
  }
  return (taken >= sz);
}
long long fib(long long n) {
  double phi = (1.0 + sqrt(5)) / 2.0;
  double res = (powl(phi, n) - powl(-phi, -n)) / sqrt(5);
  return (long long)floor(res);
}
long long count(long long total, long long running, long long a) {
  long long for_a, midcnt, right, rem;
  long long tot_sum = (total) * (running) - (((running) * (running + 1)) / 2);
  long long left = (total - 1) % a, lval = 0, rval = 0, midval = 0;
  rem = max(running - (left + 1), 0LL);
  midcnt = rem / a;
  right = rem % a;
  rval = (right)*a - (((right) * (right + 1)) / 2);
  lval = (((left) * (left + 1)) / 2);
  midval = midcnt * (((a) * (a - 1)) / 2);
  for_a = tot_sum - (lval + midval + rval);
  for_a /= a;
  for_a += running;
  return for_a;
}
pair<long long, pair<long long, long long> > dfs(
    vector<vector<long long> > &adj, long long curr, vector<long long> &vis,
    long long total, long long running, long long a, long long b, long long lcm,
    vector<long long> &va, vector<long long> &vb, vector<long long> &vl) {
  vis[curr] = 1;
  pair<long long, pair<long long, long long> > sum = {0, {0, 0}};
  bool isleaf = true;
  for (long long i = 0; i < adj[curr].size(); i++) {
    if (i == 0) {
      pair<long long, pair<long long, long long> > temp;
      temp = dfs(adj, adj[curr][i], vis, total + 1, running + 1, a, b, lcm, va,
                 vb, vl);
      sum.first += temp.first;
      sum.second.first += temp.second.first;
      sum.second.second += temp.second.second;
    } else {
      pair<long long, pair<long long, long long> > temp;
      temp = dfs(adj, adj[curr][i], vis, total + 1, 1, a, b, lcm, va, vb, vl);
      sum.first += temp.first;
      sum.second.first += temp.second.first;
      sum.second.second += temp.second.second;
    }
    isleaf = false;
  }
  if (isleaf) {
    long long for_a = count(total, running, a);
    long long for_b = count(total, running, b);
    long long for_lcm = count(total, running, lcm);
    sum = {for_lcm, {for_a, for_b}};
  }
  va[curr] = sum.second.first;
  vb[curr] = sum.second.second;
  vl[curr] = sum.first;
  return sum;
}
void solve() {
  string s;
  cin >> s;
  vector<long long> num;
  char pre = '0';
  long long cnt = 0;
  for (long long i = 0; i < s.size(); ++i) {
    if (s[i] == '0') {
      if (cnt > 0) {
        num.push_back(cnt);
        cnt = 0;
      }
    } else {
      cnt++;
    }
  }
  if (cnt > 0) {
    num.push_back(cnt);
    cnt = 0;
  }
  sort(num.rbegin(), num.rend());
  long long alice = 0;
  for (long long i = 0; i < num.size(); ++i) {
    if (i % 2 == 0) {
      alice += num[i];
    }
  }
  cout << alice << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  int t;
  cin >> t;
  for (long long t1 = 0; t1 < t; ++t1) {
    solve();
  }
  return 0;
}

```