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
//Mateusz Piórkowski
#include <iostream>
#include <vector>
#include <algorithm>

//#define DEBUG

struct city_gap{
	int size;
	int infected_sides;
};

struct city_gap_compare {
    bool operator()(city_gap a, 
                    city_gap b) const {
        return a.size*(3-a.infected_sides) > b.size*(3-b.infected_sides);
    }
};

void print_city_gaps(std::vector<city_gap> &city_gaps){
	for(city_gap gap : city_gaps){
		std::cout << gap.size << " " << gap.infected_sides << "\n";
	}
}

int solve(std::vector<city_gap> &city_gaps, int already_infected){
	int vaccinated=0;
	int total_infected=already_infected;
	while(1){
		//for(city_gap* gap : city_gaps){ //vaccinate
		for(auto it=city_gaps.begin(); it!=city_gaps.end(); ++it){
			city_gap& gap = *it;
			if((gap.infected_sides>0) && (gap.size>0)){ //can vaccinate
				gap.infected_sides--;
				gap.size--;
				vaccinated+=1;

				//city_gaps.erase(it);
				//city_gaps.insert(gap);
				break;
			}
		}
		//std::sort(city_gaps.begin(), city_gaps.end(), city_gap_compare());
		int day_infected=0;
		//for(city_gap* gap : city_gaps){
		for(auto it=city_gaps.begin(); it!=city_gaps.end(); ++it){
			city_gap& gap = *it;
			int infected;
			infected=std::min(gap.infected_sides, gap.size);
			gap.size-=infected;
			day_infected+=infected;
			
			//city_gaps.erase(it);
			//city_gaps.insert(gap);
		}
		//std::sort(city_gaps.begin(), city_gaps.end(), city_gap_compare());
		#ifdef DEBUG
		std::cout << "Today infected: " << day_infected << "\n";
		#endif
		if(day_infected==0) break;
		total_infected+=day_infected;
	}
	return total_infected;
}

int main(){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	int testn;
	std::cin >> testn;
	for(int test=0; test<testn; test++){
		std::vector<city_gap> city_gaps;
		int n;
		std::cin >> n;
		std::string city;
		std::cin >> city;
		bool edge=true;
		int size=0;
		int already_infected=0;
		for(int i=0; i<city.length(); i++){
			if(city[i] == '1'){//Found infected
				already_infected+=1;
				if(size!=0){
					city_gaps.push_back({size,2-edge});
					size=0;
				}
				edge=false;
			}else{//Found healthy
				size+=1;
			}
		}
		if(size!=0){ //Last gap
			edge=true;
			city_gaps.push_back({size,2-edge});
		}
		#ifdef DEBUG
		print_city_gaps(city_gaps);
		#endif
		std::sort(city_gaps.begin(), city_gaps.end(), city_gap_compare());
		std::cout << solve(city_gaps, already_infected) << "\n";
	}
}