#include<bits/stdc++.h>
using namespace std;

#define MAXN 500005
#define int long long

int fl[MAXN][3][3];
int fr[MAXN][3][3];
int p[MAXN];
char a[MAXN];
int n;

void mx(int &x,int y) {
    if(x < y) x = y;
}
void mn(int &x,int y) {
    if(y < 0) y = 0;
    if(x > y) x = y;
}


signed main() {
    int T;
    cin >> T;
    while(T --) {
        scanf("%s",a+1);
        n = strlen(a+1);
        for(int i = 0; i <= n+1; i ++) {
            fl[i][0][0] = 1e18;
            fl[i][0][1] = 1e18;
            fl[i][1][0] = 1e18;
            fl[i][1][1] = 1e18;
            fr[i][0][0] = 1e18;
            fr[i][0][1] = 1e18;
            fr[i][1][0] = 1e18;
            fr[i][1][1] = 1e18;
            
            p[i] = 0;
            fr[i][0][1] = -1;
            fr[i][1][1] = -1;
        }
        p[0] = 1;

        for(int i = 1; i <= n; i ++) {
            if(a[i] != '1') {
                if(p[i-1] == 1) {
                    fl[i][0][1] = 1; 
                    mx(fr[i][0][1],1);
                }
                mn(fl[i][1][1],fl[i-1][0][0]-1);
                mn(fl[i][1][0],fl[i-1][0][1]-1);
                mn(fl[i][0][1],fl[i-1][1][0]+1);
                mn(fl[i][0][0],fl[i-1][1][1]+1);

                mx(fr[i][1][1],fr[i-1][0][0]-1);
                mx(fr[i][1][0],fr[i-1][0][1]-1);
                mx(fr[i][0][1],fr[i-1][1][0]+1);
                mx(fr[i][0][0],fr[i-1][1][1]+1);


                if(fl[i][0][0] == 0 || fl[i][1][0] == 0) p[i] = 1;
            } 
            if(a[i] != '0') {
                if(p[i-1] == 1) {
                    fl[i][1][1] = 1;
                    mx(fr[i][1][1],1);
                }
                mn(fl[i][1][1],fl[i-1][0][0]+1);
                mn(fl[i][1][0],fl[i-1][0][1]+1);
                mn(fl[i][0][1],fl[i-1][1][0]-1);
                mn(fl[i][0][0],fl[i-1][1][1]-1);

                mx(fr[i][1][1],fr[i-1][0][0]+1);
                mx(fr[i][1][0],fr[i-1][0][1]+1);
                mx(fr[i][0][1],fr[i-1][1][0]-1);
                mx(fr[i][0][0],fr[i-1][1][1]-1);

                if(fl[i][0][0] == 0 || fl[i][1][0] == 0) p[i] = 1;
              
            }
    
            if(p[i]) {
                if(fr[i][0][0] >= 2) fl[i][0][0] = 2;
                else fl[i][0][0] = 1e18;
                if(fr[i][1][0] >= 2) fl[i][1][0] = 2;
                else fl[i][1][0] = 1e18;
                
            }
         /*   cout<<i<<" "<<p[i]<<"---\n";
                cout<<fl[i][0][0]<<" "<<fl[i][0][1]<<" "<<fl[i][1][0]<<" "<<fl[i][1][1]<<"\n";
                cout<<fr[i][0][0]<<" "<<fr[i][0][1]<<" "<<fr[i][1][0]<<" "<<fr[i][1][1]<<"\n";
           */ //if(p[i]) fl[i][0][0] = fl[i][1][0] = 0;     
        }
        if(p[n]) cout<<0<<"\n";
        else cout<<min({fl[n][0][0],fl[n][0][1],fl[n][1][0],fl[n][1][1]})<<"\n";
    }

}
/*
5
0110101
01020102
0000021111
1012121010
0100202010
*/