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

const int MAXN = 100000;

#define FOR(i, n) for(int i = 0, __n = (n); i < __n; i++)

char T[MAXN+2];

int counter[MAXN+1];

int main() {
  ios_base::sync_with_stdio(0);

  int t; cin >> t;

  FOR(t1, t) {
    int n;
    cin >> n;

    cin >> T;
    int MX = 0;
    int cnt = 0;
    int c1 = 0, c2 = 0;
    FOR(i, n) {
      if (T[i] == '0') {
        cnt ++;
      } else {
        if (i == cnt) {
          // MX = max(MX, cnt);
          // counter[cnt]++;
          c1 = cnt;
        } else {
          MX = max(MX, cnt);
          counter[cnt]++;
        }
        cnt = 0;
      }
    }
    if (cnt > 0) {
      if (cnt == n) {
        cout << 0 << endl;
        continue;
      } else {
        c2 = cnt;
      }
    }

    // FOR(i, MX+1) {
    //   cerr << counter[i] << " ";
    // }
    // cerr << endl;
    if (c1 < c2) swap(c1, c2);

    int days = 0;
    int sum = 0;
    int i = MX;
    for (; i > days || c1 > days;) {
      // cerr << i << " d=" << days << " c1=" << c1 << " " << counter[i] << endl;
      if (c1 > days && (i < 0 || (c1 - days)*2 >= i - 2*days)) {
        sum += c1 - days;
        // cerr << "side " << c1 << " d=" << days<< endl;
        c1 = c2; c2 = 0;
        days ++;
      } else if (counter[i] > 0) {
        if(i >= 2*days + 2) {
          sum += i - (2*days) - 1;
          // cerr << "inside " << i << " d=" << days << " => " << i - (2*days) - 1 << endl;
          days +=2;
        } else if(i == 2*days + 1) {
          sum ++;
          // cerr << "last" << endl;
          days ++;
        }
        counter[i] --;
      } else {
        i--;
      }

    }
    cout << n - sum << endl;

    FOR(i, MX+1)  counter[i] = 0;
  
  }
}