#include <bits/stdc++.h>

using namespace std;

// Type Aliases for readability
using ll = long long;

/**
 * Calculates the cumulative cost to transform the string based on a target character.
 * @param target: The character we want to process (e.g., '0' or '1')
 * @param s: The input string
 * @param n: String length
 * @return A vector containing the cumulative cost at each position
 */
vector<ll> calculate_costs(char target, const string& s, ll n) {
    vector<ll> costs(n, 0);
    ll current_penalty = 0;

    for (ll i = 0; i < n; ++i) {
        // Get the cost from the previous position if it exists
        ll previous_cost = (i > 0) ? costs[i - 1] : 0;

        if (s[i] == target) {
            // Logic: if current char matches target, add penalty and reset it
            ll extra_cost = (current_penalty * 2) + 1;
            costs[i] = previous_cost + extra_cost;
            current_penalty = 0;
        } else {
            // Otherwise, increase the penalty for the next match
            current_penalty++;
            costs[i] = previous_cost;
        }
    }
    return costs;
}

/**
 * Finds the minimum combined cost from forward and backward passes.
 * Note: Since 'backward' is reversed, we align costs[i] with backward_costs[n-1-i]
 */
ll find_min_combined_cost(const vector<ll>& forward, const vector<ll>& backward, ll n) {
    ll min_total = LLONG_MAX;

    for (ll i = 0; i < n; ++i) {
        // Aligning forward index i with its corresponding backward index
        ll combined = forward[i] + backward[n - 1 - i];
        min_total = min(min_total, combined);
    }
    return min_total;
}

void solve() {
    ll n;
    if (!(cin >> n)) return;
    string s;
    cin >> s;

    // Create a reversed version of the string for backward calculation
    string reversed_s = s;
    reverse(reversed_s.begin(), reversed_s.end());

    // Calculate costs for both '0' and '1' in both directions
    vector<ll> forward_zeros = calculate_costs('0', s, n);
    vector<ll> backward_zeros = calculate_costs('0', reversed_s, n);

    vector<ll> forward_ones = calculate_costs('1', s, n);
    vector<ll> backward_ones = calculate_costs('1', reversed_s, n);

    // Get the minimums for each target character
    ll min_zero_cost = find_min_combined_cost(forward_zeros, backward_zeros, n);
    ll min_one_cost = find_min_combined_cost(forward_ones, backward_ones, n);

    // Output the overall minimum
    cout << min(min_zero_cost, min_one_cost) << "\n";
}

int main() {
    // Optimization for fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int test_cases = 1;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}