#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e6+7;
int t;
int n;
int dp1[MAXN][2];
int dp2[MAXN][2];
string a;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	cin>>t;
	while(t--)
	{
		cin>>a;
		n=a.size();
		a=' '+a;
		for(int i=0;i<=n;i++)
		{
			dp1[i][0]=dp1[i][1]=-1e9;
			dp2[i][0]=dp2[i][1]=1e9;
		}

		dp1[0][0]=dp1[0][1]=0;
		dp2[0][0]=dp2[0][1]=0;
		if(a[1]=='1') dp1[1][1]=dp2[1][1]=1;
		else if(a[1]=='0') dp1[1][0]=dp2[1][0]=1;
		else
		{
			dp1[1][1]=dp2[1][1]=1;
			dp1[1][0]=dp2[1][0]=1;
		}

		for(int i=2;i<=n;i++)
		{
			if(a[i-1]=='2'||a[i]==a[i-1])
			{
				dp1[i][0]=max(dp1[i][0],dp1[i-2][0]);
				dp1[i][1]=max(dp1[i][1],dp1[i-2][1]);
				dp2[i][0]=min(dp2[i][0],dp2[i-2][0]);
				dp2[i][1]=min(dp2[i][1],dp2[i-2][1]);
			}
			if(a[i]=='2')
			{
				if(dp1[i-1][1]>0) dp1[i][0]=max(dp1[i][0],dp1[i-1][1]-1);
				if(dp1[i-1][1]>0&&dp1[i-1][1]>=-1e6) dp2[i][0]=min(dp2[i][0],dp1[i-1][1]-1);
				if(dp2[i-1][1]>0) dp2[i][0]=min(dp2[i][0],dp2[i-1][1]-1);
				dp1[i][1]=max(dp1[i][1],dp1[i-1][0]+1);
				dp2[i][1]=min(dp2[i][1],dp2[i-1][0]+1);

				if(dp1[i-1][0]>0) dp1[i][1]=max(dp1[i][1],dp1[i-1][0]-1);
				if(dp1[i-1][0]>0&&dp1[i-1][0]>=-1e6) dp2[i][1]=min(dp2[i][1],dp1[i-1][0]-1);
				if(dp2[i-1][0]>0) dp2[i][1]=min(dp2[i][1],dp2[i-1][0]-1);
				dp1[i][0]=max(dp1[i][0],dp1[i-1][1]+1);
				dp2[i][0]=min(dp2[i][0],dp2[i-1][1]+1);
			}
			else if(a[i]=='1')
			{
				if(dp1[i-1][1]>0) dp1[i][0]=max(dp1[i][0],dp1[i-1][1]-1);
				if(dp1[i-1][1]>0&&dp1[i-1][1]>=-1e6) dp2[i][0]=min(dp2[i][0],dp1[i-1][1]-1);
				if(dp2[i-1][1]>0) dp2[i][0]=min(dp2[i][0],dp2[i-1][1]-1);
				dp1[i][1]=max(dp1[i][1],dp1[i-1][0]+1);
				dp2[i][1]=min(dp2[i][1],dp2[i-1][0]+1);
			}
			else
			{
				if(dp1[i-1][0]>0) dp1[i][1]=max(dp1[i][1],dp1[i-1][0]-1);
				if(dp1[i-1][0]>0&&dp1[i-1][0]>=-1e6) dp2[i][1]=min(dp2[i][1],dp1[i-1][0]-1);
				if(dp2[i-1][0]>0) dp2[i][1]=min(dp2[i][1],dp2[i-1][0]-1);
				dp1[i][0]=max(dp1[i][0],dp1[i-1][1]+1);
				dp2[i][0]=min(dp2[i][0],dp2[i-1][1]+1);
			}
			if(dp2[i][0]==0||dp2[i][1]==0)
			{
				dp2[i][0]=dp2[i][1]=0;
				dp1[i][0]=max(dp1[i][0],0);
				dp1[i][1]=max(dp1[i][1],0);
			}
			if(dp1[i][0]==0||dp1[i][1]==0)
			{
				dp1[i][0]=dp1[i][1]=0;
				dp2[i][0]=dp2[i][1]=0;
			}
		}
		// for(int i=1;i<=n;i++) cerr<<i<<" "<<dp2[i][0]<<" "<<dp1[i][0]<<" "<<dp2[i][1]<<" "<<dp1[i][1]<<" sad"<<endl;
		int ans=n;
		for(int i=1;i<=n;i++)
		{
			int s2=min(dp2[i][0],dp2[i][1]);
			ans=min(ans,n-i+s2);

		}
		cout<<ans<<'\n';
	}
	return 0;
}
/*
1
0120120101
2

1
0210012101
*/