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
#include<bits/stdc++.h>
#define ST first
#define ND second
#define ll long long
#define ld long double
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using namespace std;
 
const ll  INF = 1e9 + 9;
const ll  MOD = 1e9 + 7;
const long long LINF = (ll)1e18 + 3;

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int tt; cin >> tt;
    while(tt--){
        int n; cin >> n;
        string s; cin >> s;
        priority_queue<int> firstType, secondType;
        int cnt = 0, ind1 = -1, ind2 = -1;
        for(int i = 0; i < n; i++){
            if(s[i] == '1'){
                ind1 = i;
                break;
            } else {
                cnt++;
            }
        }
        if(cnt != 0) firstType.push(cnt);
        cnt = 0;
        for(int i = n - 1; i >= 0; i--){
            if(s[i] == '1'){
                ind2 = i;
                break;
            } else {
                cnt++;
            }
        }
        if(cnt != 0) firstType.push(cnt);
        if(cnt == n){
            cout << 0 << "\n";
            continue;
        }
        cnt = 0;
        for(int i = ind1; i <= ind2; i++){
            if(s[i] == '1'){
                if(cnt != 0){
                    secondType.push(cnt);
                }
                cnt = 0;
            } else {
                cnt++;
            }
        }
        int uratowane = 0, days = 0;
        while(firstType.size() || secondType.size()){
            if(firstType.size()){
                if(secondType.size()){
                    int x = firstType.top() - days;
                    int y = secondType.top() - 2 * days;
                    if(x * 2 >= y){
                        x = firstType.top();
                        if(x - days > 0){
                            uratowane += (x - days);
                        }
                        firstType.pop();
                    } else {
                        x = secondType.top();
                        if(x - 2*days > 0){
                            uratowane++;
                            firstType.push(x - 2*days - 1 + days);
                        }
                        secondType.pop();
                    }
                } else {
                    int x = firstType.top();
                    if(x - days > 0){
                        uratowane += (x - days);
                    } else {
                        break;
                    }
                    firstType.pop();
                }
            } else {
                int x = secondType.top();
                if(x - 2*days > 0){
                    uratowane++;
                    firstType.push(x - 2*days - 1 + days);
                } else {
                    break;
                }
                secondType.pop();
            }
            days++;
        }
        cout << n - uratowane << "\n";
    }

	return 0;
}