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
/*
 *  Copyright (C) 2021  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


struct Gap {
	int length;
	int open;

	float score() const {
		if (open == 2) {
			return 0.5 * (length - 1);
		}
		return length;
	}

	int operator<(const Gap& other) const {
		if (this->score() == other.score()) {
			return length > other.length;
		}
		return this->score() > other.score();
	}
};


int solve(vector<int>& infected, int n) {
	int size = infected.size();
	if (size == 0) {
		return 0;
	}

	vector<Gap> gaps;
	gaps.reserve(size);

	gaps.push_back({infected[0], 1});
	gaps.push_back({n - infected[size - 1] - 1, 1});
	for (int i = 1; i < size; ++i) {
		int diff = infected[i] - infected[i-1] - 1;
		if (diff > 0) {
			gaps.push_back({diff, 2});
		}
	}

	sort(gaps.begin(), gaps.end());

	int days = 0;
	int immune = 0;

	for (auto gap:gaps) {
		int save = gap.length - days;

		// edge gap, can be protected with single immunisation
		if (gap.open == 1) {
			days += 1;
		}
		else {
			save -= days;
			// special case, gap of length 1
			if (save == 1) {
				days += 1;
			}
			// need to block both ends
			else {
				save -= 1;
				days += 2;
			}
		}

		if (save <= 0) {
			break;
		}
		immune += save;
	}
	return n - immune;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	int n;
	char status;
	vector<int> infected;

	while (t-- > 0) {
		cin >> n;
		infected.clear();

		for (int i = 0; i < n; ++i) {
			cin >> status;
			if (status == '1') {
				infected.push_back(i);
			}
		}

		cout << solve(infected, n) << endl;
	}

	return 0;
}