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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct zero_sequence
{
int l,d;

int operator<(const zero_sequence &y) const
	{
		if (this->l - this->d == y.l - y.d) return this->d < y.d;
		else return this->l > y.l;
	}
};

typedef struct zero_sequence zeros;
typedef vector<zeros> zerosv;

int main()
{
char C[50001];
int T,t,N,n,a,f;
zeros tmp;
zerosv Z;
zerosv::iterator it,it2;


	scanf("%d",&T);
	for (t = 0; t < T; t++)
	{
		scanf("%d",&N);
		scanf("%s",C);
		
		Z.clear();
		if (C[0] == '0')
		{
			f = 1;
			a = 0;
			tmp.d = 0;
		} else
		{
			f = 0;
		}
		for (n = 1; n < N; n++)
		{
			if (C[n] == '0' && f == 0)
			{
				f = 1;
				a = n;
				tmp.d = 1;
			}
			else if (C[n] == '1' && f == 1)
			{
				f = 0;
				tmp.l = n-a;
				tmp.d++;
				Z.push_back(tmp);
			}
		}
		if (f == 1) 
		{
			tmp.l = n-a;
			Z.push_back(tmp);
		}

//////////////////////////////////////////////////
/*		
		printf("%d %s\n",N,C);
		for (it = Z.begin(); it != Z.end(); ++it)
		{
			printf("%d %d\n",it->l,it->d);
		}
		printf("\n");
*/		
		sort(Z.begin(),Z.end());
		
		f = 0;
		for (it = Z.begin(); it != Z.end() && it->d > 0; ++it)
		{
			it->l -= f*it->d + it->d-1;
			if (it->l == 0) it->l = 1;
			f += it->d;				
			it->d = 0;
/*			
for (it2 = Z.begin(); it2 != Z.end(); ++it2)
{
	printf("%d %d\n",it2->l,it2->d);
}
printf("\n");
*/
		}
		
		f = 0;
		for (it = Z.begin(); it != Z.end() && it->l > 0; ++it)
		{
			f += it->l;
		}		
/*
		for (it = Z.begin(); it != Z.end(); ++it)
		{
			printf("%d %d\n",it->l,it->d);
		}
		printf("\n");
*/
		printf("%d\n",N-f);
//		printf("\n");
	}
	
	
	return 0;
}