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
#include <iostream>
#include <set>
#include <vector>

struct Pas {
	int wielkosc = 0;
	int spadek = 0;

	bool operator <(const Pas &pas) const {
		return (3*wielkosc + spadek) < (3*pas.wielkosc + pas.spadek);
	}
};

typedef std::vector<Pas> Pasy;

void wypisz(Pasy pasy) {
	for (Pas &pas : pasy) {
		std::cerr << "||" << pas.wielkosc << " Δ" << pas.spadek << std::endl;
	}
	std::cerr << std::endl;
}

int mastodont(const Pasy &pasy) {
	int wynik = 0;
	bool koniec = true;
	int zaszczepionych = 0;
	std::set<Pas> szczepione;
//	wypisz(pasy);
	for (int i = 0; i < pasy.size(); ++i) {
		zaszczepionych += pasy[i].wielkosc;
		if (pasy[i].spadek == 0 || pasy[i].wielkosc == 0 || szczepione.find(pasy[i]) != szczepione.end()) {
			continue;
		}
		koniec = false;
		szczepione.insert(Pas{pasy[i]});
   		Pasy nowepasy = pasy;
		if (nowepasy[i].wielkosc == 1) {
			nowepasy[i].spadek = 0;
		} else {
			nowepasy[i].spadek--;
		}
		for (Pas &pas : nowepasy) {
			pas.wielkosc -= pas.spadek;
			if (pas.wielkosc < 0) {
				pas.wielkosc = 0;
			}
		}
		int tu = mastodont(nowepasy);
		if (wynik < tu) {
			wynik = tu;
		}
	}
	if (koniec && wynik < zaszczepionych) {
		wynik = zaszczepionych;
	}
	return wynik;
}

void zaszczep() {
	std::string miasta;
	std::vector<Pas> pasy;
	int miast;

	std::cin >> miast >> miasta;

	miasta = "2" + miasta + "2";

	char poprzednie = '2';

	for (char miasto : miasta) {
		if (miasto == '0') {
			if (poprzednie == '0') {
				pasy.rbegin()->wielkosc++;
			} else if (poprzednie == '1') {
				pasy.push_back({1, 1});
			} else if (poprzednie == '2') {
				pasy.push_back({1, 0});
			}
		} else if (miasto == '1') {
			if (poprzednie == '0') {
				pasy.rbegin()->spadek++;
			}
		}
		poprzednie = miasto;
	}

//	wypisz(pasy);
	int wynik = mastodont(pasy);
	std::cout << (miast - wynik) << std::endl;
}

int main() {
	int testow;

	std::cin >> testow;
	for (int i = 0; i < testow; ++i) {
		zaszczep();
	}
	return 0;
}