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
126
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int tt;
    cin >> tt;

    while (tt--) {

        int n, sum = 0, minn = INT_MAX;
        string s;

        priority_queue <int> V;
        priority_queue <int> P;

        cin >> n >> s;

        int i = n - 1;

        while (s[i] != '1' && i >= 0) i--;

        if (i != n - 1 && s[i] == '1')
            P.push(n - 1 - i);

        i = 0;

        while (s[i] != '1' && i < n) i++;

        if (i != 0 && s[i] == '1')
            P.push(i);

        int ilezer = 0;

        for (; i < n; i++) {

            if (s[i] == '1') {
                if (ilezer != 0)
                    V.push(ilezer);
                ilezer = 0;
            } else {
                ilezer++;
            }
        }

        if (V.empty() && P.empty()) {

            if (s[0] == '1')
                cout << n << endl;
            else
                cout << 0 << endl;

            continue;
        }

        priority_queue <int> V_ = V;
        priority_queue <int> P_ = P;


        for (int j = 0; j < 4; j++) {

            sum = 0;

            P = P_;
            V = V_;
            int i;

            switch (j) {

                case 0:
                    if (P.size() == 2) {
                        for (i = 0; !P.empty(); i++) {
                            sum += P.top() - i;
                            P.pop();
                        }
                    } else continue;
                    break;
                case 1:
                    if (!P.empty()) {
                        sum += P.top();
                        i = 1;
                    } else continue;
                    break;
                case 2:
                    if (P.size() == 2) {

                        P.pop();
                        sum += P.top();
                        i = 1;
                    } else continue;
                    break;
                case 3:
                    i = 0;
            }

            while (!V.empty()) {

                //cout << sum << endl;

                if (V.top() - 2*i == 1) {
                    sum += 1;
                } else {

                    sum += max(0, V.top() - 2*i - 1);
                }

                if (V.top() -2*i != 1 && V.top() -2*i != 2)
                    i++;

                V.pop();
                i++;

                //cout << sum << endl;
            }

            minn = min(minn, n - sum);
        }

        cout << minn << endl;




    }
    return 0;
}