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 <queue>

int Z, n, c, o;
bool start;
std::priority_queue<int> q0, q1;
std::string s;

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin >> Z;
	while(Z--)
	{
		while( !q0.empty() ) q0.pop();
	       	while( !q1.empty() ) q1.pop();	
		std::cin >> n >> s;
		c = 0;
		o = 0;
		start = ( s[0] == '0' );		
		for( int i = 0; i < s.size(); i++)
		{
			if( s[i] == '0' )	c++;
			else if( !start )
			{
				if( c != 0 )	q0.push(c);
				c = 1;
				while( (i < s.size() ) && s[i] != '0' )
				{
					i++;
					o++;
				}
			}
			else
			{
				start = false;
				q1.push(c);
				c = 1;
				while( (i < s.size()) && s[i] != '0' )
				{
					i++;
					o++;
				}
			}
		}
		if( s[s.size()-1] == '0' )	q1.push(c);
		if( start )
		{
			std::cout << "0\n";
			continue;
		}
		int res = 0;
		int i = 0;
		int curr, curr1;
		while( !q0.empty() || !q1.empty() )
		{
			if( q0.empty() )
			{
				curr = q1.top();
				if( curr - i > 0 )
				{
					i++;
					res += i;
				}
				else res += curr;
				q1.pop();
			}
			else if( q1.empty() )
			{
				curr = q0.top();
				if( curr - 2*i > 0 )
				{
					i++;
					res += i;
					q1.push(curr - i);
				}
				else res += curr;
				q0.pop();
			}
			else
			{
				curr = q0.top();
				curr1 = q1.top();
				if( curr - 2*i > curr1 - i )
				{
					if( curr - 2*i > 0 )
					{
						i++;
						res += i;
						q1.push(curr - i);
					}
					else res += curr;
					q0.pop();
				}
				else
				{
				       	if( curr1 - i > 0 )
					{
						i++;
						res += i;
					}
					else res += curr1;
					q1.pop();
				}

			}
		}
		std::cout << o + res - i << '\n';

	}	
	return 0;
}