1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, p, k) for(int i(p); i < k; ++i)
typedef long long int ll;
typedef long double ld;
template <typename T = int> inline T in()
{
    T x;
    std::cin >> x;
    return x;
}
int rob(int n)
{
    std::vector <std::pair <int, int>> w{};
    int c(0), d(0), odp(0);
    while(n--)
    {
        if(in<char>() == '1')
        {
            w.push_back({c, 1 + !!w.size()});
            c = 0;
            ++odp;
        }
        else ++c;
    }
    w.push_back({c, 1});
    std::sort(w.begin(), w.end(), [](const auto& a, const auto& b){
		return a.first * b.second > b.first * a.second;
	});
	//for(auto i: w)std::cerr << i.first<<' '<<i.second<<'\n';
    for(auto i: w)
    {
        if(d * i.second >= i.first){
            odp += i.first;
            continue;
        }
        odp += d * i.second;
        i.first -= d * i.second;
		++d;
		if(i.second == 2)
		{
			if(i.first > 1)++odp;
			if(i.first > 2)++d;
		}
    }
    return odp;
}
int main()
{
    std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0);
    int t(in());
    while(t--)std::cout << rob(in())<<'\n';
    return 0;
}