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
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 100000;
int t, n, cnm[MAX_N + 1], lncm, lastn, w, poc, kon;
char c, lc;
bool pn, on;

bool cmp(int &fi, int&se)
{
	if (fi <= se)return false;
	return true;
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin >> t;
	for (; t >= 1; t--)
	{
		cin >> n >> c;
		if (1 == n)
		{
			if ('0' == c)
			{
				cout << "1\n";
				continue;
			}
			cout << "0\n";
			continue;
		}
		lncm = 0;
		lastn = 0;
		if ('0' == c)
		{
			pn = true;
			lastn++;
		}
		if ('1' == c)
		{
			pn = false;
		}
		for (int i = 1; i < n - 1; i++)
		{
			lc = c;
			cin >> c;
			if ('1' == c)
			{
				if ('1' == lc)continue;
				cnm[lncm] = lastn;
				lncm++;
				lastn = 0;
				continue;
			}
			lastn++;
		}
		lc = c;
		cin >> c;
		if ('1' == c)
		{
			on = false;
			if ('0' == lc)
			{
				cnm[lncm] = lastn;
				lncm++;
				lastn = 0;
			}
		}
		else
		{
			on = true;
			cnm[lncm] = lastn + 1;
			lncm++;
		}
		if (1 == lncm && (true == on || true == pn))
		{
			cout << n-cnm[0]<<"\n";
			continue;
		}
		poc = 0;
		kon = lncm-1;
		if (true == pn)
		{
			cnm[0] *= 2;
			poc++;
		}
		if (true == on)
		{
			cnm[lncm - 1] *= 2;
			kon--;
		}
		for (int i = poc; i <= kon; i++)
		{
			cnm[lncm] = cnm[i];
			lncm++;
		}
		sort(cnm, cnm + lncm, cmp);
		w = 0;
		for (int i = 0; i < lncm; i++)
		{
			if (2 * i >= cnm[i])break;
			w += cnm[i];
			w -= 2 * i;
		}
		w += w % 2;
		w /= 2;
		cout << n-w<<"\n";
	}
}