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
#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main()
{
    string line;
    int t, n, left, right, zeros=0, days = 0, alive = 0, current;
    bool getNew = false;
    priority_queue<int> pq;
    cin>>t;
    for(int i=0; i<t; i++) {
        zeros = 0;
        left = right = -1;
        cin>>n;
        cin>>line;
        for (int j=0; j<n; j++) {
            if (line[j] == '0') {
                zeros++;
            } else {
                if (left == -1) {
                    left = zeros;
                } else if (zeros > 0) {
                    pq.push(zeros);
                }
                zeros = 0;
            }
        }
        if (zeros > 0) {
            right = zeros;
        }
        getNew = true;
        current = -1;
        days = 0;
        alive = 0;
        while (!pq.empty()) {
            
            if (getNew) {
                current = pq.top() - days;
                pq.pop();
            }
            
            if (current > left && current > right && current > 0) {
                if (current > 3) {
                    alive = alive + current - 1;
                    days += 4;
                    left -= 2;
                    right -= 2;
                } else if (current == 3) {
                    if (left == 2 || right == 2) {
                        alive += 3;
                        left = right = -1;
                        current =-1;
                        break;
                    }  else {
                        alive += 2;
                        left = right = -1;
                        current =-1;
                        break;
                    }  
                } 
                else if (current > 0) {
                    alive++;
                    days++;
                    left = right = -1;
                    current =-1;
                    break;
                } else {
                    current =-1;
                    break;   
                }
                getNew = true;
            }
            else if (left >= current && left > right && left > 0) {
                alive += left;
                days += 2;
                current -= 2;
                right--;
                left = -1;
                getNew = false;
            } else if (right > 0) {
                alive += right;
                days += 2;
                current -= 2;
                left--;
                right = -1;    
                getNew = false;
            } else {
                getNew = true;
            }
        }
        if (!getNew && current >0 && current <= 2) {
            alive++;
        } else if (!getNew && current > 2) {
            alive = alive + current -1;
        }
        if (left > 0 && left > right) {
            alive += left;
            right--;
        }
        if (right > 0) {
            alive += right;   
        }
        pq = priority_queue <int>();
        cout<<n-alive<<endl;
    }

}