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
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <string.h>
#include <vector>

// int count(const std::vector<char> &v) {
//  int result = 0;
//  for (size_t i = 0; i < v.size(); ++i) {
//    if (v[i] == '1') {
//      result++;
//    }
//  }
//  return result;
//}

void print(const std::string &str, const std::vector<char> &v) {
  std::cerr << str << ": ";
  for (char c : v) {
    std::cerr << c;
  }
  std::cerr << std::endl;
}

int count_epidemic(const std::vector<char> &v) {
  int result = 0;
  for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] == '1') {
      result++;
    }
  }
  return result;
}

std::set<int> get_indexes(const std::vector<char> &v) {
  std::set<int> s;
  for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] == '0' &&
        ((i > 0 && v[i - 1] == '1') || (i < v.size() - 1 && v[i + 1] == '1'))) {
      s.insert(i);
    }
  }
  return s;
}

void process(const std::vector<char> &v, const std::set<int> &indexes,
             int epidemic, int &min, bool expand) {
  std::vector<char> copy = v;
  std::set<int> next_indexes;

  // DEBUG
//  print("1", copy);

  int count = 0;

  if (expand) {
    for (int i : indexes) {
      if (copy[i] == '1' || copy[i] == '2') {
        continue;
      }

      copy[i] = '1';
      count++;

      if (i > 0 && copy[i - 1] == '0') {
        next_indexes.insert(i - 1);
      }
      if (i < (int)v.size() - 1 && copy[i + 1] == '0') {
        next_indexes.insert(i + 1);
      }
    }

    if (epidemic + count >= min) {
      return;
    }

    if (memcmp(copy.data(), v.data(), v.size()) == 0) {
      min = std::min(min, epidemic + count);
      return;
    }
  } else {
    next_indexes = indexes;
  }

  // DEBUG
//  print("2", copy);

  for (int i : next_indexes) {
    if (copy[i] != '0') {
      continue;
    }
    copy[i] = '2';
    process(copy, next_indexes, epidemic + count, min, true);
    copy[i] = '0';
  }
}

int main() {
  int T = 0;
  std::cin >> T;

  for (int i = 0; i < T; ++i) {
    int N = 0;
    std::cin >> N;

    std::vector<char> v(N);

    for (int j = 0; j < N; ++j) {
      std::cin >> v[j];
    }

    int min = std::numeric_limits<int>::max();

    std::set<int> indexes = get_indexes(v);
    int epidemic = count_epidemic(v);

    // DEBUG
    fprintf(stderr, "e: %d, i: %zd\n", epidemic, indexes.size());

    process(v, indexes, epidemic, min, false);

    std::cout << (min == std::numeric_limits<int>::max() ? 0 : min)
              << std::endl;
  }

  return 0;
}