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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int,int>;
using vpii = vector<pii>;
using graph = vector<vi>;

#define FOR(name__, upper__) for (int name__ = 0; name__ < (upper__); ++name__)
#define all(x) begin(x), end(x)
#define mp make_pair
#define mt make_tuple

const int inf = 1e9;

void go() {
    int n; cin >> n;
    string s; cin >> s;

    vi one, two;
    int i = 0, j = 0;
    while (i < n && s[i] == '1') i++;

    int ones = 0;
    for (char x : s) if (x == '1') ones++;

    if (ones == n) { cout << n << '\n'; }
    else if (ones == 0) { cout << 0 << '\n'; }
    else {

        while (i < n) {
            j = i + 1;

            while (j < n && s[j] == s[i]) j++;

            if (s[i] == '0') {
                if (i == 0 || j == n) {
                    one.push_back(j - i);
                }
                else {
                    two.push_back(j - i);
                }
            }
            i = j;
        }

        sort(all(one));
        reverse(all(one));
        sort(all(two));
        reverse(all(two));

        int possible = 0;
        int turns = 0;

        for (int i = 0; i < one.size(); i++) {
            if (one[i] - i > 0) {
                possible += one[i] - i;
                turns++;
            }
        }

        for (int i = 0; i < two.size(); i++) {
            if (two[i] - 2 * turns > 0) {
                int from_ones = 0;

                for (int i = 0; i < one.size(); i++) {
                    if (one[i] - i > 0) {
                        possible += one[i] - i - turns;
                    }
                }

                int my_sum = max(1, two[i] - 2 * turns - 1);

                possible += max(1, two[i] - 2 * turns - 1);
                turns++;
            }
            for (int i = 0; i < one.size(); i++) {
                if (one[i] - i > 0) {
                    possible += one[i] - i;
                    turns++;
                }
            }
        }

        
        cout << n - possible << '\n';
    }
}

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(0);
    
    int t; cin >> t;
    while (t--) go();

	return 0;
}