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
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<long long>(a, b)(rng)

#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define f first
#define s second
#define pb push_back

#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define vvii vector<vii>

#define ll long long

const int N = 1e6 + 7;

int score2(int dl){
    if(dl >= 3)
        return dl - 1;
    else
        return max(dl, 0);
}

void solve(){
    int n; cin >> n;


    string s;
    cin >> s;

    string t = s;
    sort(all(t));
    
    if(t[0] == t.back()){
        if(t[0] == '0'){
            cout << 0 << '\n';
        }
        else{
            cout << n << '\n';
        }
        return;
    }

    vector<int> dwojki;
    vector<int> jedynki;

    int ost = -1;
    
    for(int i = 0; i < n; i++){
        if(s[i] == '1'){
            if(ost != i - 1){
                if(ost == -1)
                    jedynki.pb(i);
                else
                    dwojki.pb(i - ost - 1);
            }
            ost = i;
        }
    }

    if(ost != n - 1)
        jedynki.pb(n - ost - 1);

    jedynki.pb(0);
    dwojki.pb(0);
    sort(all(jedynki));
    sort(all(dwojki));

    int ans = 0;

    int ind_jed = 0;
    int ind_dwa = 0;

    while(true){
        int s1 = sz(jedynki) ? jedynki.back() * 2 : 0;
        int s2 = sz(dwojki) ? score2(dwojki.back()) : 0;

        if(max(s1, s2) == 0)
            break;

        if(s1 > s2){
            ans += jedynki.back();
            jedynki.pop_back();
        }
        else{
            jedynki.push_back(dwojki.back() - 1);
            dwojki.pop_back();
            ans++;
        }

        for(int i = ind_dwa; i < sz(dwojki); i++){
            dwojki[i] = max(0, dwojki[i] - 2);
            if(dwojki[i] == 0)
                ind_dwa++;
        }
        
        for(int i = ind_jed; i < sz(jedynki); i++){
            jedynki[i] = max(0, jedynki[i] - 1);
            if(jedynki[i] == 0)
                ind_jed++;
        }
    }

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

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

    int tests = 1;
    cin >> tests;

    for(int i = 0; i < tests; i++)
        solve();

    return 0;
}