#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5e6+5,M=(1<<20)+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
char s[N];int n;
pii s1[N],s2[N];int h1,h2,st[N],sh;
ll f[N],dp[N][2];
ll calc(int x,int ox,int y,int oy){
	int w=0;ll tot=0;
	int z=x;
	while(s2[z+1].se==s2[z].se) z++;
	if(ox) w+=(s2[x].fi-s2[x-1].fi)/4*4,tot+=1ll*(s2[x].fi-s2[x-1].fi)/4*(z-x+1);
	if(!oy) w+=(s2[y+1].fi-s2[y].fi)/4*4,tot+=1ll*(s2[y+1].fi-s2[y].fi)/4*(y-z);
	w+=s2[z+1].fi-s2[z].fi-1;
	return f[w]+tot;
}
void chkmax(ll &x,ll y){if(y>x) x=y;}
void Solve(){
	int i,j;scanf("%s",s+3);
	s[1]=s[2]='1';n=strlen(s+1);s[n+1]=s[n+2]='0';n+=2;
	h1=h2=0;for(i=1;i<n;i++) if(s[i]==s[i+1]) s1[++h1]=make_pair(i,s[i]);
	ll ans=0;
	// for(i=1;i<=h1;i++) gdb(s1[i].fi,s1[i].se);
	for(i=1;i<=h1;i++){
		s2[++h2]=s1[i];
		if(h2>=2&&s2[h2-1].se=='0'&&s2[h2].se=='1'&&(s2[h2].fi-s2[h2-1].fi)%4==0) ans+=(s2[h2].fi-s2[h2-1].fi)/4,h2-=2;
	}
	for(i=2;i<=h2;i++) if(s2[i-1].se=='1'&&s2[i].se=='1'){
		int w=s2[i].fi-s2[i-1].fi>>2;
		ans+=w;s2[i].fi-=w*4;
	}
	for(i=h2-1;i;i--) if(s2[i].se=='0'&&s2[i+1].se=='0'){
		int w=s2[i+1].fi-s2[i].fi>>2;
		ans+=w;s2[i].fi+=w*4;
	}
	for(i=5;i<=n;i++){
		int w=(i-5+1)/4;
		f[i]=f[3+w*4]+w+1;
	}
	st[sh=1]=0;for(i=1;i<h2;i++) if(s2[i].se=='0'&&s2[i+1].se=='1') st[++sh]=i;st[++sh]=h2;
	for(i=1;i<=sh;i++) Me(dp[i],-0x3f)/*,gdb(st[i],s2[st[i]].fi)*/;
	dp[1][0]=0;
	for(i=2;i<=sh;i++){
		for(int x:{0,1}) for(int y:{0,1}) chkmax(dp[i][x],dp[i-1][y]+calc(st[i-1]+1,y,st[i],x));
	}
	printf("%lld\n",dp[sh][1]+ans);
}
int main(){
	int t=1;
	scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}