1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>    // std::sort

int t;
char* chars = new char[100001];
int n;
int ones_front_count;
int ones_back_count;

std::vector<int> four_or_more_counts;
std::vector<int> three_or_less_counts;
std::vector<int> bound_counts;

int front_count() {
  int i =0;
  while (chars[i] == '0') { i++; }
  return i;
}

int back_count() {
  int i = 0;
  while (chars[n-i-1] == '0') { i++; }
  return i;
}

int total_ones_count() {
  int ones_count = 0;
  for (int j=0; j<n; j++) {
    if (chars[j] == '1') {
      ones_count++;
    }
  }
  return ones_count;
}

void collect_counts() {
  ones_front_count = front_count();
  ones_back_count = back_count();
  if (ones_back_count > 0) {
    bound_counts.push_back(ones_back_count);
  }
  if (ones_front_count > 0) {
    bound_counts.push_back(ones_front_count);
  }
  int last_one_index = -1;

  for (int i=0; i<n; i++) {
    if (chars[i] == '1') {
      if (last_one_index >= 0) {
        int count = i - last_one_index - 1;
        if (count > 0) {
          if (count >= 4) {
            four_or_more_counts.push_back(count);
          } else {
            three_or_less_counts.push_back(count);
          }
        }
      }
      last_one_index = i;
    }
  }
}

int main() {
  scanf("%d\n", &t);
  for (int i=0; i < t; i++) {
    scanf("%d\n", &n);
    char c;
    for (int j=0; j<n; j++) {
      scanf("%c", &c);
      chars[j] = c;
    }
    scanf("\n");
  //  printf("==============\n");
    int ones_count = total_ones_count();
    if (ones_count == 0) {
      // printf("=====");
      printf("0\n");
    } else {
      bound_counts.clear();
      four_or_more_counts.clear();
      three_or_less_counts.clear();
      int new_ones_count = 0;
      int iteration = 0;
      collect_counts();
      std::sort (four_or_more_counts.begin(), four_or_more_counts.end(), std::greater<>());

      // for (int j=0; j<four_or_more_counts.size(); j++) {
      //   printf("four_or_more_counts=%d\n", four_or_more_counts[j]);
      // }

      // for (int j=0; j<three_or_less_counts.size(); j++) {
      //   printf("three_or_less_counts=%d\n", three_or_less_counts[j]);
      // }

      if (bound_counts.size() == 2 && bound_counts[0] + bound_counts[1] >= 4) {
        for (int j=0; j<bound_counts.size(); j++) {
          int zero_count = bound_counts[j];
          int remaining_zero_count = zero_count - iteration;
          if (remaining_zero_count <= 0) { // consumed already completely, nothing to do anymore more
            //printf("zero_count for bound: %d- adding all zeros %d\n", zero_count, zero_count);
            new_ones_count += zero_count;
          } else {  // 1 or more left - makes sense to use both iterations
        // printf("zero_count for bound: %d - adding iteration count: %d\n", zero_count, iteration);
            new_ones_count += (zero_count - remaining_zero_count);
            iteration ++;
          }
        }
        bound_counts.clear();
      }

      for (int j=0; j<four_or_more_counts.size(); j++) {
        int zero_count = four_or_more_counts[j];
        int remaining_zero_count = zero_count - 2*iteration;
        if (remaining_zero_count <= 0 ) { // consumed already completely, nothing to do anymore more
          new_ones_count += zero_count;
        } else if (remaining_zero_count < 4) { // four or less left, just push it back to dedicated queue
          three_or_less_counts.push_back(zero_count);
        } else { // 4 or more left - makes sense to use both iterations
          new_ones_count += (zero_count - remaining_zero_count) + 1;
          iteration += 2;
        }
      }

      //printf("after processing long: %d, %d\n", new_ones_count, iteration);

      for (int j=0; j<bound_counts.size(); j++) {
        int zero_count = bound_counts[j];
        int remaining_zero_count = zero_count - iteration;
        if (remaining_zero_count <= 0) { // consumed already completely, nothing to do anymore more
          //printf("zero_count for bound: %d- adding all zeros %d\n", zero_count, zero_count);
          new_ones_count += zero_count;
        } else {  // 1 or more left - makes sense to use both iterations
       // printf("zero_count for bound: %d - adding iteration count: %d\n", zero_count, iteration);
          new_ones_count += (zero_count - remaining_zero_count);
          iteration ++;
        }
      }
    //  printf("after processing bounds: %d, %d\n", new_ones_count, iteration);

      for (int j=0; j<three_or_less_counts.size(); j++) {
        int zero_count = three_or_less_counts[j];
        int remaining_zero_count = zero_count - 2*iteration;
        if (remaining_zero_count <= 0 ) { // consumed already completely, nothing to do anymore more
          new_ones_count += zero_count;
        } else if (remaining_zero_count == 1) { // single left, lets save him in one iteration
          new_ones_count += (zero_count - remaining_zero_count);
          iteration ++;
        } else if (remaining_zero_count == 2) {
          new_ones_count += (zero_count - remaining_zero_count + 1);
          iteration ++;
        } else { // remaining_zero_count == 3
          new_ones_count += (zero_count - remaining_zero_count + 1);
          iteration += 2;
        }
      }
    //  printf("after processing shorts: %d, %d\n", new_ones_count, iteration);


      // printf("ones_front_count: %d, ones_back_count=%d, iteration=%d\n", ones_front_count, ones_back_count, iteration);
      // printf("=====");
      printf("%d\n", ones_count + new_ones_count);
    }
  }

  return 0;
}