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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> w1, w2;

int licz0(int kk)
{
  int u=0, a2=w2.size()-1;
  for (int k=kk; ;)
  {
      int u2= 0<=a2 ? w2[a2]-2*k : -1;
      if (u2<=0)
          break;
      if (u2<=2)
      {
          ++u;
          ++k;
          --a2;
          continue;
      }
      u+=u2-1;
      k+=2;
      --a2;
  }
  return u;
}

int licz1()
{
    if (w1.size()<1)
        return -1;
    return w1[w1.size()-1]+licz0(1);

}

int licz2()
{
    if (w1.size()<2)
        return -1;
    return w1[0]+w1[1]-1+licz0(2);
}

void xx()
{
    int n;
    string s;
    cin>>n>>s;
    w1.clear();
    w2.clear();
    int p1=-1;
    for (int i=0; i<n; ++i)
        if (s[i]=='1')
        {
            int ile=i-p1-1;
            if (0<ile)
            {
                if (p1==-1) w1.push_back(ile);
                else w2.push_back(ile);
            }
            p1=i;
        }
    if (p1==-1)
    {
        cout<<"0\n";
        return;
    }
    if (p1<n-1)
        w1.push_back(n-p1-1);

    sort(w1.begin(), w1.end());
    sort(w2.begin(), w2.end());

    int a=licz0(0), b=licz1(), c=licz2();
    int u=max(a, max(b, c));
    cout<<(n-u)<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    for (int i=0; i<t; ++i)
        xx();
    return 0;
}