#include <bits/stdc++.h>
#define ll long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define SORT(v) sort(v.begin(), v.end())
#define REVERSE(v) reverse(v.begin(), v.end())
#define REV_SORT(v) sort((v).begin(), (v).end(), greater<>())
#define vint vector<int>
#define vll vector<ll>
#define vch vector<char>
#define vstr vector<string>
#define u_set unordered_set
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define fast                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
using namespace std;

void debug()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}

void solve();

int32_t main()
{
    fast;
    // debug();
    int TestCase = 1;
    cin >> TestCase;
    while (TestCase--)
        solve();
    return 0;
}

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

    string S;
    cin >> S;

    int count_0 = 0;
    int count_1 = 0;

    for (char c : S)
    {
        if (c == '0')
        {
            count_0++;
        }
        else
        {
            count_1++;
        }
    }

    vint prefix_sum_0(N + 1, 0);
    vint prefix_sum_1(N + 1, 0);

    prefix_sum_0[0] = 0;
    prefix_sum_1[0] = 0;

    for (int i = 0; i < N; ++i)
    {
        prefix_sum_0[i + 1] = prefix_sum_0[i] + (S[i] == '0');
        prefix_sum_1[i + 1] = prefix_sum_1[i] + (S[i] == '1');
    }

    int non_increasing = INT_MAX;
    int non_decreasing = INT_MAX;

    for (int i = 0; i < N; ++i)
    {
        int operations_non_increasing = prefix_sum_1[i] + (count_0 - prefix_sum_0[i]);
        non_increasing = min(non_increasing, operations_non_increasing);
        int operations_non_decreasing = prefix_sum_0[i] + (count_1 - prefix_sum_1[i]);
        non_decreasing = min(non_decreasing, operations_non_decreasing);
    }
    cout << min(non_increasing, non_decreasing) << '\n';
}