#include<bits/stdc++.h>
using namespace std;
const int NR=2e5+10;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
int n;
char s[NR];
int f[NR][2][2],g[NR][2][2];
int t[NR];
void work()
{
	scanf("%s",s+1);n=strlen(s+1);
	t[0]=1;
	for(int i=1;i<=n;i++)t[i]=0;
	memset(f[0],0x3f,sizeof(f[0]));
	memset(g[0],0,sizeof(g[0]));
	for(int i=1;i<=n;i++)
	{
		memset(f[i],0x3f,sizeof(f[i]));
		memset(g[i],0,sizeof(g[i]));
		if(s[i]!='0'){
			//1
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					if(b==1){
						f[i][a][b^1]=min(f[i-1][a][b]-1,f[i][a][b^1]);
						g[i][a][b^1]=max(g[i-1][a][b]-1,g[i][a][b^1]);
					}
					else{
						f[i][a][b^1]=min(f[i-1][a][b]+1,f[i][a][b^1]);
						g[i][a][b^1]=max(g[i-1][a][b]+1,g[i][a][b^1]);
					}
					if(f[i][a][b^1]==0){
						f[i][a][b^1]++,t[i]=1;
						if(!g[i][a][b^1])f[i][a][b^1]=0x3f3f3f3f;
					}
				}
			}
			if(t[i-1])f[i][1][1]=1,g[i][1][1]=max(g[i][1][1],1);
		}
		if(s[i]!='1'){
			//0
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					if(b==0){
						f[i][a][b^1]=min(f[i][a][b^1],f[i-1][a][b]-1);
						g[i][a][b^1]=max(g[i][a][b^1],g[i-1][a][b]-1);
					}
					else{
						f[i][a][b^1]=min(f[i][a][b^1],f[i-1][a][b]+1);
						g[i][a][b^1]=max(g[i][a][b^1],g[i-1][a][b]+1);
					}
					if(f[i][a][b^1]==0){
						f[i][a][b^1]++,t[i]=1;
						if(!g[i][a][b^1])f[i][a][b^1]=0x3f3f3f3f;
					}
				}
			}
			if(t[i-1])f[i][0][0]=1,g[i][0][0]=max(g[i][0][0],1);
		}
//		for(int a=0;a<=1;a++){
//			for(int b=0;b<=1;b++){
//				printf("dp[%d][%d][%d]=%d %d\n",i,a,b,f[i][a][b],g[i][a][b]);
//			}
//		}
//		cout<<"------------------------"<<t[i]<<endl;
	}
	int ans=0x3f3f3f3f;
	if(t[n])ans=0;
	for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)ans=min(ans,f[n][i][j]);
	printf("%d\n",ans);
}
int main()
{
	int T=read();while(T--)work();
	return 0;
}
/*
5
0110101
01020102
0000021111
1012121010
0100202010
*/