#include <iostream>
#include <vector>
#include <algorithm>

struct Area {
    char prev{'b'};
    char next{'e'};
    int a{0};
    int b{0};
    bool used{false};
    void print() {
        std::cout << "p:" << prev << " n:" << next << " " << a << " " << b << '\n';
    }
};

bool operator>(const Area& l, const Area& r) {
    int free_cities_l = l.b - l.a;
    int free_cities_r = r.b - r.a;

    return free_cities_l > free_cities_r;
}

int solution(std::vector<Area>& areas, std::vector<Area> borders, int infected) {
    if (areas.empty()) {
        if(infected > 0) {
            if (borders.size() <= 1) {
                return infected;
            }

            return infected + 1;
        }
        return 0;
    }

    std::sort(areas.begin(), areas.end(), std::greater<Area>{});
    std::sort(borders.begin(), borders.end(), std::greater<Area>{});

    // std::cout << "areas: \n"; 
    // for(auto& a :areas) {
    //     a.print();
    // }
    // std::cout << "\nborders: \n"; 
    // for(auto& b : borders) {
    //     b.print();
    // }


    int day = 0;
    auto it = areas.begin();
    bool border_used = false;
    while(it != areas.end()) {
    // for(auto& area : areas) {
        auto& area = *it;
        border_used = false;

        // std::cout << loop++ << ":\n";
        int a = area.a + day;
        int b = area.b - day;
        int c_left = b - a;

        if(c_left <= 0) {
            // std::cout << "wa" << area.a << area.b << '\n';
            infected += area.b - area.a;
            ++it;
            continue;
        }

        for(auto& border : borders) {
            if(border.used) {
                continue;
            }

            int ba = border.a;
            if(border.prev != 'b') {
                ba += day;
            }

            int bb = border.b;
            if(border.next != 'e') {
                bb -= day;
            }

            int b_c_left = bb - ba;
            if(b_c_left <= 0) {
                continue;
            }

            //border is more important to save
            if(b_c_left + 2 >= c_left) {
                // std::cout << border.prev << " " << border.next << '\n';
                // std::cout << "border over area\n";

                infected += day;

                // std::cout << day << " " << infected << '\n';
                border.used = true;
                border_used = true;
                ++day;
                break;
            }
        }

        if(border_used) {
            continue;
        }

        //left is right only one vac this day for both
        if(a == b-1) {
            infected += 2*day;
            // std::cout << "one vac " << day << " " << infected << '\n';
            ++day;
            ++it;
            continue;
        }

        //vac left size, count left
        infected += day;
        // std::cout << "left " << day << " " << infected << '\n';
        ++day;
        --b;
        //count right
        infected += day;

        //right is left, no need to vac
        if(b-1 <= a) {
            ++it;
            continue;
        }

        //right was vaccinated
        ++day;
        ++it;
    }

    for (auto& border : borders) {
        if (border.used) {
            continue;
        }

        int ba = border.a;
        if (border.prev != 'b') {
            ba += day;
        }

        int bb = border.b;
        if (border.next != 'e') {
            bb -= day;
        }

        int b_c_left = bb - ba;
        if (b_c_left <= 0) {
            infected += border.b - border.a;
            continue;
        }

        infected += day;
        ++day;
    }

    return infected;
}

int main()
{
    int t;
    int n;
    std::cin >> t;
    int tc = 1;
    while(t--) {
        std::cin >> n;
        int count = 0;
        char buff;
        char prev = 'b';
        Area area;
        int i=0;
        std::vector<Area> areas;
        std::vector<Area> borders;
        while(n--) {
            std::cin >> buff;
            if(buff == '1') {
                //close current area
                if(prev == '0') {
                    area.b = i;
                    area.next = '1';
                    if(area.prev == 'b') {
                        borders.push_back(area);
                    } else {
                        areas.push_back(area);
                    }
                    area.next = 'e';
                }
                ++count;
            } else {
                //open new area
                if(prev == '1' || prev == 'b') {
                    area.prev = prev;
                    area.a = i;
                }
            }

            prev = buff;
            ++i;
        }
        //...111000
        //check if last area was closed or is open
        if(prev == '0') {
            area.b = i;
            borders.push_back(area);
        }



        std::cout << solution(areas, borders, count) << '\n';
    }


    return 0;
}