#include <cstdio>
#include <cassert>
#include <algorithm>
#include <list>

//using namespace std;

class pr {
public:
        int val;
        int cnt;
};

int n, nt;

class cities {
public:
        std::list<pr> t;

        int virus();
        void set9();
        void print();
        int calc();
};

// 0 - zdrowy
// 1 - zarażony
// 9 - zaszczepiony


int cities::virus()
{
        int chg = 0;

        for (auto it = t.begin(); it != t.end(); ++it) {
                if (it->val == 1) {
                        auto prev_it = std::prev(it);
                        auto next_it = std::next(it);

                        if (prev_it->val == 0) {
                                if (prev_it->cnt > 0) {
                                        prev_it->cnt--;
                                        it->cnt++;
                                        chg = 1;
                                }
                        }
                        if (next_it->val == 0) {
                                if (next_it->cnt > 0) {
                                        next_it->cnt--;
                                        it->cnt++;
                                        chg = 1;
                                }
                        }
                }
        }

        auto it = t.begin();
        while (it != t.end()) {
                if (it->val == 0 && it->cnt == 0) {
                        it = t.erase(it);
                } else {
                        it++;
                }
        }

        for (auto it = t.begin(); it != t.end(); ++it) {
                std::list<pr>::iterator next_it;

                if (it->val != 1) {
                        continue;
                }

                while (1) {
                        next_it = std::next(it);
                
                        if (next_it == t.end()) {
                                break;
                        }

                        if (next_it->val != 1) {
                                break;
                        }
        
                        it->cnt += next_it->cnt;
                        t.erase(next_it);
                }
        }

        return chg;
}



void cities::set9()
{
        int bestlen = 0;
        int curlen;
        int cur_left;
        int best_left;

        std::list<pr>::iterator it;
        std::list<pr>::iterator bestpos = t.end();

        it = t.begin();
        while(1) {
                std::list<pr>::iterator prev_it;
                std::list<pr>::iterator next_it;

                while(it != t.end() && it->val != 0) {
                        it++;
                }

                if (it == t.end()) {
                        break;
                }

                prev_it = std::prev(it);
                next_it = std::next(it);

                if (prev_it->val == 9 && next_it->val == 9) {
                        // znaleziomy przedział zdrowych miast jest już uratowany
                        // bo z obydwu stron ma kontakt z miastem zaszczepionym
                        it++;
                        continue;
                }

                if (prev_it->val == 9) {
                        // miasto na lewo od znalezionego przedziału jest zaszczepione
                        // na prawo zarażone
                        // dokładamy +2 do znalezionej pozycji bo o tyle jest lepsza od pozycji
                        // w której obydwa końce przedziału są zarażone
                        curlen = it->cnt+2;
                        cur_left = 0;
                } else {
                        if (next_it->val == 9) {
                                curlen = it->cnt+2;
                                cur_left = 1;
                        } else {
                                // z obydwu stron zarażone
                                curlen = it->cnt;
                                cur_left = 1;
                        }
                }
                if (curlen > bestlen) {
                        bestlen = curlen;
                        bestpos = it;
                        best_left = cur_left;
                }
                it++;
        }

        if (bestpos != t.end()) {
                pr p;

                p.val = 9;
                p.cnt = 1;
        
                if (best_left == 1) {
                        t.insert(bestpos, p);
                        bestpos->cnt--;
                } else {
                        it = std::next(bestpos);
                        t.insert(it, p);
                        bestpos->cnt--;
                }
        }
}



int cities::calc()
{
        int chg;

//        print();
        while(1) {
                set9();
//                print();
                chg = virus();
//                print();
                if (chg == 0) {
                        break;
                }
        }

        for(auto x : t) {
                if (x.val == 1) {
                        chg += x.cnt;
                }
        }
        return chg;
}


void cities::print()
{
        for (auto x : t) {
                printf(" %d(%d)", x.val, x.cnt);
        }
        printf("\n");
}

int main()
{
        int i, j;
        cities c;
        pr p;

        scanf("%d\n", &nt);
        for(i = 0; i < nt; ++i) {
                scanf("%d\n", &n);
                c.t.clear();
                p.val = 9;
                p.cnt = 1;
                for(j = 0; j < n; ++j) {
                        char ch;

                        scanf("%c", &ch);
                        ch -= '0';
                        if (ch == p.val) {
                                p.cnt++;
                                continue;
                        }                 
                        c.t.push_front(p);
                        p.val = ch;
                        p.cnt = 1;
                }
                c.t.push_front(p);
                p.val = 9;
                p.cnt = 1;
                c.t.push_front(p);
                printf("%d\n", c.calc());
        }
 
        return 0;
}