#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;

const int INF = 1000000009;
const LL LINF = 1000000000000000009LL;

#define FOR(i, b, e) for (int i = b; i <= e; ++i)
#define FORD(i, b, e) for (int i = b; i >= e; --i)
#define REP(i, n) FOR (i, 0, n - 1)
#define REV(i, n) FORD (i, n - 1, 0)
#define PB push_back
#define PP pop_back
#define MP make_pair
#define MT make_tuple
#define ST first
#define ND second
#define SZ(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()
#define UNIQ(c) (c).erase(unique(ALL(c)), (c).end());

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/hash_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; /*find_by_order() order_of_key()*/

template <typename T, typename S>
ostream &operator<<(ostream &out, const pair<T, S> &v)
{
    return (out << "(" << v.ST << ", " << v.ND << ")");
}

#define DEBUG(s) s
#ifdef local_comp
#define PRINT(V) cout << "#" << #V << ": " << V << endl;
#else
#define PRINT(v)
#endif

const int N = 1000005;

int n, t;

VI process(string s)
{
    VI res;
    int cnt = 0;
    REP (i, SZ(s))
    {
        if (s[i] == '0') { cnt++; }
        else
        {
            if (cnt > 0) res.PB(cnt);
            cnt = 0;
        }
    }
    if (cnt > 0) res.PB(cnt);
    return res;
}

int test_before1(VI x, int x0, int x1)
{
    int res = 0;
    int cnt = 0;
    if (x0 > 0)
    {
        res += x0;
        cnt++;
    }

    REV (i, SZ(x))
    {
        int tmp = x[i];
        if (tmp - 2 * cnt <= 0)
        {
            break;
        }
        else if (tmp - 2 * cnt == 1)
        {
            res++;
            cnt++;
            break;
        }

        res += tmp - 1 - 2 * cnt;
        cnt += 2;
    }

    return res;
}

int test_before2(VI x, int x0, int x1)
{
    int res = 0;
    int cnt = 0;
    if (x0 > 0)
    {
        res += x0;
        cnt++;
    }
    if (x1 > 1)
    {
        res += x1 - 1;
        cnt++;
    }

    REV (i, SZ(x))
    {
        int tmp = x[i];
        if (tmp - 2 * cnt <= 0)
        {
            break;
        }
        else if (tmp - 2 * cnt == 1)
        {
            res++;
            cnt++;
            break;
        }

        res += tmp - 1 - 2 * cnt;
        cnt += 2;
    }

    return res;
}

int test_after1(VI x, int x0, int x1)
{
    int res = 0;
    int cnt = 0;

    REV (i, SZ(x))
    {
        int tmp = x[i];

        if (tmp - 2 * cnt <= 0)
        {
            break;
        }
        else if (tmp - 2 * cnt == 1)
        {
            res++;
            cnt++;
            break;
        }

        res += tmp - 1 - 2 * cnt;
        cnt += 2;
    }

    res += max(0, x0 - cnt);
    res += max(0, x1 - cnt - 1);
    return res;
}

int test_after2(VI x, int x0, int x1)
{
    int res = 0;
    int cnt = 0;

    REV (i, SZ(x))
    {
        int tmp = x[i];

        if (tmp - 2 * cnt <= 1)
        {
            break;
        }

        res += tmp - 1 - 2 * cnt;
        cnt += 2;
    }

    res += max(0, x0 - cnt);
    res += max(0, x1 - cnt - 1);
    return res;
}

int main()
{
#ifndef local_comp
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> t;
    while (t--)
    {
        cin >> n;
        string s;
        cin >> s;
        auto x = process(s);
        if (SZ(x) == 0)
        {
            cout << n << "\n";
            continue;
        }
        if (SZ(x) == 1)
        {
            int xx = x.back();
            if (xx == n)
            {
                cout << "0\n";
            }
            else if(xx == 1)
            {
                cout << n - 1 << "\n";
            }
            else if (s.front() == '1' && s.back() == '1')
            {
                cout << n - xx + 1 << "\n";
            }
            else
            {
                cout << n - xx << "\n";
            }

            continue;
        }
        // for (auto it : x)
        //     cout << it << " ";
        // cout << "\n";

        int xf = s.front() == '0' ? x.front() : 0;
        int xb = s.back() == '0' ? x.back() : 0;

        int x0 = max(xf, xb);
        int x1 = min(xf, xb);

        if (xb > 0) x.PP();
        swap(x.front(), x.back());
        if (xf > 0) x.PP();
        sort(ALL(x));

        int b1 = test_before1(x, x0, x1);
        int b2 = test_before2(x, x0, x1);
        int a1 = test_after1(x, x0, x1);
        int a2 = test_after2(x, x0, x1);

        // int c = SZ(s);
        // cout << b1 << " " << b2 << " " << a1 << " " << a2 << " | " << x0 << " " << x1 << "\n";

        int res = max(max(a1, a2), max(b1, b2));
        cout << n - res << "\n";
    }

    return 0;
}
/*

1001000010
2, 4, 2






*/