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
#include <bits/stdc++.h>
using namespace std;
int t,n,i,cur,cnt,m,lst,lft,rgh,res,a[100100];
char s[100100];
bool check(int n, int d) {
  return (d>=3*n && d<=6*n);
}
int solve(int steps) {
  int res=0;
  for (int i=0; i<m; i++) {
    int cur=a[i]-steps*2;
    if (cur==1 || cur==2) {
      res+=a[i]-1;
      ++steps;
    } else if (cur>0) {
      res+=a[i]-cur+1;
      steps+=2;
    } else res+=a[i];
  }
  return res;
}
int main() {
  scanf("%d",&t);
  while (t--) {
    scanf("%d",&n);
    scanf("%s",s);
    lst=-1;
    lft=rgh=0;
    for (cnt=cur=m=i=0; i<n; i++) if (s[i]=='1') {
      if (cur>0) {
        if (lst==-1) lft=cur; else a[m++]=cur;
        cur=0;
      }
      lst=i;
      ++cnt;
    } else ++cur;
    if (lst==-1) { puts("0"); continue; }
    if (cur>0) rgh=cur;
    sort(a,a+m);
    reverse(a,a+m);
    res=solve(0)+lft+rgh;
    if (lft+rgh>0) res=min(res,solve(1)+min(lft,rgh));
    if (lft>0 && rgh>0 && lft+rgh>2) res=min(res,solve(2)+1);
    printf("%d\n",res+cnt);
  }
  return 0;
}