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
120
121
122
123
#include <bits/stdc++.h>
#define gc getchar
#define gcu getchar_unlocked
#define fi first
#define se second
#define pb push_back
#define mod ((ll)1e9 + 7)
typedef long long ll;
using namespace std;
//=============================================

int n, m;
void zad(void);

//=============================================
int main()
{
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
		zad();
}
//=============================================
void zad(void)
{
	scanf("%d", &n);
	gc();
	int ans = n;
	int czas = 0;
	priority_queue<int> q1;
	priority_queue<pair<int, int>> q2;
	{
		int temp = 0;
		for (int i = 0; i < n; i++)
		{
			char c = gc();
			if (c == '0')
				temp++;
			else if (temp)
			{
				if (temp == i)
					q1.push(temp);
				else
				{
					if (temp % 2)
						q2.push({temp / 2 + 1, temp / 2});
					else
						q2.push({temp / 2, temp / 2});
				}
				temp = 0;
			}
		}
		if (temp)
			q1.push(temp);
	}
	while (!q1.empty() || !q2.empty())
	{
		if (!q1.empty())
		{
			if (q1.top() - czas <= 0)
			{
				while (!q1.empty())
					q1.pop();
				continue;
			}
		}
		else
		{
			while (!q2.empty())
			{
				if (q2.top().fi - czas > 0)
					ans -= q2.top().fi - czas;
				else
					break;
				czas++;
				if (q2.top().se - czas > 0)
					ans -= q2.top().se - czas;
				else
					break;
				czas++;
				q2.pop();
			}
			break;
		}
		if (!q2.empty())
		{
			if (q2.top().fi - czas <= 0)
			{
				while (!q2.empty())
					q2.pop();
				continue;
			}
		}
		else
		{
			while (!q1.empty())
			{
				if (q1.top() - czas > 0)
					ans -= q1.top() - czas;
				else
					break;
				czas++;
				q1.pop();
			}
			break;
		}
		if (q1.top() >= q2.top().fi)
		{
			ans -= q1.top() - czas;
			czas++;
			q1.pop();
		}
		else
		{
			ans -= q2.top().fi - czas;
			czas++;
			if (q2.top().se - czas > 0)
				ans -= q2.top().se - czas;
			czas++;
			q2.pop();
		}
	}
	printf("%d\n", ans);
}