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
124
125
#include <cstdio>
#include <queue>


using namespace std;

char c;

int main()
{
	int t, n, ones = 0;
	scanf("%d\n", &t);
	for (int T = 0; T < t; T++)
	{
		priority_queue<int> q;

		scanf("%d\n", &n);
		
		int free = 0, first_len;
		bool first = true;
		
		for (int i = 0; i < n; i++)
		{
			scanf("%c", &c);
			if (c == '1')
			{
				if (first)
				{
					first_len = free;
					first = false;
				}
				else
				{
					q.push(free);
				}
				free = 0;
			}
			else
			{
				free++;
			}
		}

		if (first)
		{
			printf("%d\n", 0);
			continue;
		}

		int last_len = free;
		if (q.size() == 0)
		{
			if (first_len == 0 || last_len == 0)
			{
				printf("%d\n", n - first_len - last_len);
			}
			else
			{
				printf("%d\n", n - first_len - last_len + 1);
			}

			continue;
		}


		int border0 = 0;
		int lost0 = 1;

		int border1 = max(first_len, last_len);
		int lost1 = 3;

		int border2 = max(first_len + last_len - 1, 0);
		int lost2 = 5;

		

		while (q.size()) 
		{
			int a = q.top();
			q.pop();

			if (a == lost0)
			{
				border0 ++;
			} else
			if (a - lost0 > 0)
			{
				border0 += (a - lost0);
			}
			else
			{
				break;
			}

			if (a == lost1)
			{
				border1++;
			} else
			if (a - lost1 > 0)
			{
				border1 += (a - lost1);
			}

			if (a == lost2)
			{
				border2++;
			}
			else
			if (a - lost2 > 0)
			{
				border2 += (a - lost2);
			}

			lost0 += 4;
			lost1 += 4;
			lost2 += 4;
		}

		border0 = max(border0, max(border1, border2));
		printf("%d\n", n-border0);

	}

	return 0;
}