#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
bool memBeg;
template<typename T> void chkmin(T &x,T y) {if(x>y) x=y;}
template<typename T> void chkmax(T &x,T y) {if(x<y) x=y;}
constexpr int mod=1e9+7;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,int times) {
    int ret=1;
    for(;times;times>>=1,x=1ll*x*x%mod) {
        if(times&1) ret=1ll*ret*x%mod;
    }
    return ret;
}
constexpr int maxn=5e6+15;
int n;
char s[maxn],t[maxn];
pair<int,char> stk[maxn];
ll ret,cot[maxn];
bool memEn;
void fl() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
void solve(){
    // fprintf(stderr,"%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
    // fl();
    scanf("%s",s+1);
    n=strlen(s+1);
    int top=0;
    ll ret=0ll;
    // 0...1 -> .....
    auto emplace=[&](int idx,char c) {
        if(top&&stk[top].second=='0'&&c=='1'&&((idx-stk[top].first)&3)==0) {
            ret+=(idx-stk[top].first)>>2; top--;
        } else stk[++top]={idx,c};
    };
    emplace(0,'1');
    if(s[1]=='1') emplace(1,'1');
    for(int i=2;i<=n;i++) if(s[i]==s[i-1]) emplace(i,s[i]);
    if(s[n]=='0') emplace(n+1,'0');
    emplace(n+2,'0');
    // 0.... -> ....0
    for(int i=top-1;i>=1;i--) {
        if(stk[i].second=='0'&&stk[i+1].second=='0') {
            int t=(stk[i+1].first-stk[i].first)>>2;
            ret+=t; stk[i].first+=t<<2;
        }
    }
    // ....1 -> 1....
    for(int i=2;i<=top;i++) {
        if(stk[i].second=='1'&&stk[i-1].second=='1') {
            int t=(stk[i].first-stk[i-1].first)>>2;
            ret+=t; stk[i].first-=t<<2;
        }
    }
    // printf("ret = %lld\n",ret);
    for(int i=6;i<=n+2;i++) {
        int t=(i-2)>>2;
        cot[i]=t+cot[t<<2];
    }
    int ept[2]={-1,-1};
    ll mx[2]={0ll,0ll};
    for(int i=1,i0,i1;i<=top;i=i1) {
        for(i0=i;i0<=top&&stk[i0].second=='0';i0++);
        for(i1=i0;i1<=top&&stk[i1].second=='1';i1++);
        if(i==1) {
            ept[0]=ept[1]=stk[i1-1].first;
        } else if(i1==top+1) {
            for(int t=0;t<2;t++) mx[t]+=cot[stk[i].first-ept[t]];
        } else {
            int nept[2]={-1,-1};
            ll nmx[2]={0ll,0ll};
            int step=(stk[i0].first-stk[i0-1].first)>>2;
            // 0.....1 -> ....0.1
            nept[0]=stk[i1-1].first;
            for(int t=0;t<2;t++) {
                chkmax(nmx[0],mx[t]+cot[(stk[i].first+(step<<2))-ept[t]]+1ll*(i0-i)*step);
            }
            // 0.....1 -> 0.1....
            nept[1]=stk[i1-1].first-(step<<2);
            for(int t=0;t<2;t++) {
                chkmax(nmx[1],mx[t]+cot[stk[i].first-ept[t]]+1ll*(i1-i0)*step);
            }
            memcpy(ept,nept,sizeof(int)*2);
            memcpy(mx,nmx,sizeof(ll)*2);
        }
    }
    printf("%lld\n",ret+max(mx[0],mx[1]));
}
int main()
{
    int _;scanf("%d",&_);
    while(_--)solve();
}