#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define ep emplace
#define pii pair<int,int>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mems(arr,x) memset(arr,x,sizeof(arr))
#define memc(arr1,arr2) memcpy(arr1,arr2,sizeof(arr2))
using namespace std;
const int maxn=2e5+10,inf=1e9;
char a[maxn];
int n;
pii dp[maxn][2];bool f[maxn];
inline void getdp(int &x,int y){(x>y)&&(x=y);}
int res,ans;
void dfs(string s){
    res=min(res,(int)s.length()-1);
    int len=s.length();
    for(int i=2;i<len;i++){
        if(s[i]==s[i-1])
            dfs(s.substr(0,i-1)+s.substr(i+1,len-i-1));
    }
}
string s;
void dfs1(int x){
    if(x>n){
        res=n+1;
        dfs(s);
        if(ans>res){
            ans=res;
        }
        return;
    }
    if(s[x]=='2'){
        s[x]='1';
        dfs1(x+1);
        s[x]='0';
        dfs1(x+1);
        s[x]='2';
    }
    else    return dfs1(x+1);
}
void solve(){
    scanf("%s",a+1);n=strlen(a+1);
    if(n<=10){
        s=" ";
        ans=n+1;
        for(int i=1;i<=n;i++)   s+=a[i];
        dfs1(1);
        printf("%d\n",ans);
        return;
    }
    dp[1][0]=dp[1][1]=pii(inf,inf);
    if(a[1]=='0'||a[1]=='2')    dp[1][0]=pii(1,1);
    if(a[1]=='1'||a[1]=='2')    dp[1][1]=pii(1,1);
    for(int i=2;i<=n;i++){
        f[i]=false;
        if(a[i]=='1'){
            dp[i][1]=pii(dp[i-1][0].fi+1,dp[i-1][0].se+1);
            if((dp[i-1][1].fi^dp[i-1][1].se)||(dp[i-1][1].fi!=1)) dp[i][0]=pii(max(1,dp[i-1][1].fi-1),max(1,dp[i-1][1].se-1));
            else    dp[i][0]=pii(inf,inf);
            if(dp[i-1][1].fi==1)    f[i]=true;
        }
        if(a[i]=='0'){
            dp[i][0]=pii(dp[i-1][1].fi+1,dp[i-1][1].se+1);
            if((dp[i-1][0].fi^dp[i-1][0].se)||(dp[i-1][0].fi!=1)) dp[i][1]=pii(max(1,dp[i-1][0].fi-1),max(1,dp[i-1][0].se-1));
            else    dp[i][1]=pii(inf,inf);
            if(dp[i-1][0].fi==1)    f[i]=true;
        }
        if(a[i]=='2'){
            if(dp[i-1][1].fi==dp[i-1][1].se&&dp[i-1][1].fi==1)  dp[i][0]=pii(2,dp[i-1][1].se+1);
            else dp[i][0]=pii(max(1,dp[i-1][1].fi-1),dp[i-1][1].se+1);
            if(dp[i-1][1].fi==1)    f[i]=true;
            if(dp[i-1][0].fi==dp[i-1][0].se&&dp[i-1][0].fi==1)  dp[i][0]=pii(2,dp[i-1][0].se+1);
            else dp[i][1]=pii(max(1,dp[i-1][0].fi-1),dp[i-1][0].se+1);
            if(dp[i-1][0].fi==1)    f[i]=true;
        }
        if(f[i-1]){
            if(a[i]=='0'||a[i]=='2'){dp[i][0].fi=1;if(dp[i][0].se>i) dp[i][0].se=1;}
            if(a[i]=='1'||a[i]=='2'){dp[i][1].fi=1;if(dp[i][1].se>i) dp[i][1].se=1;}
        }
        // printf("[%d,%d] [%d,%d] %d\n",dp[i][0].fi,dp[i][0].se,dp[i][1].fi,dp[i][1].se,f[i]);
    }
    if(!f[n])printf("%d\n",min(dp[n][0].fi,dp[n][1].fi));
    else    puts("0");
}
int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
}