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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>

#define prt(tekscik) std::cout << tekscik << std::endl 
#define FOR(i, w) for(int i = 0; i < w; i++)


void calculate(int d) {

             // 
    std::vector<std::pair<int, bool>> odleglosci;
    

    std::string c;
    std::cin >> c;
    int last = -1;
    int loc = 0;

    int ilosc_wirusow = 0;


    bool poczatek = true;
    for(char a : c) {
        if (a == '1') {
            if(!poczatek) odleglosci.push_back(std::make_pair(-ceil((loc - last - 1)), 0));
            else {
                odleglosci.push_back(std::make_pair(-ceil(loc - last - 1), 1));
                poczatek = false;
            }
            ilosc_wirusow++;
            last = loc;
            
        }

        loc++;
    }
    int max_tama = ilosc_wirusow * 2;
    
    if (!poczatek) {
        odleglosci.push_back(std::make_pair(-ceil(loc - last - 1), 1));
    }
    std::sort(odleglosci.begin(), odleglosci.end());


    int zaciesnianie = 0;
    int szczepienia = 0;



    for (std::pair<int, bool> odl : odleglosci) {
        
        int odl_element = - odl.first;
        
        
        //std::cout << "Analiza! " << odl_element << " " << odl_element - zaciesnianie * 2 - 1 << std::endl;
        if (odl_element - zaciesnianie * 2 < 0) break;
        
        if (!odl.second) {
            szczepienia += odl_element - zaciesnianie * 2 - ((odl_element - zaciesnianie * 2 >= 2) ? 1 : 0);
        }
        else {
            szczepienia += odl_element - zaciesnianie;
        }
        zaciesnianie += 1;
    }
    if (zaciesnianie == 0) {
        std::cout << "0" << std::endl;
    }
    else 
    std::cout << c.length() - szczepienia << std::endl;
}


int main()
{
    
    
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    
    int n;
    std::cin >> n;
    FOR(i, n) {
        int d;
        std::cin >> d;
        calculate(d);
    }
}