#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    string s;
    cin>>s;
    int n=s.size();
    if(n==1){
        cout<<1<<"\n";
        return;
    }
    stack<int>st;
    for(int i=0;i<n;++i){
        int x=s[i]-'0';
        if(!st.empty() && x!=2 && st.top()==x){
            st.pop();
        }
        else st.push(x);
    }
    vector<int>a;
    while(!st.empty()){
        a.push_back(st.top());
        st.pop();
    }
    int sz=a.size();
    int r[3]={0,0,0};
    int cur=0;
    for(int i=1;i<sz;i+=2){
        if(a[i]==2) continue;
        a[i]^=1;
    }
    for(int i=0;i<sz;++i) r[a[i]]++;
    int ma=max(r[0],r[1]),mi=min(r[0],r[1]);
    if(mi+r[2]>=ma){
        int ans=r[0]+r[1]+r[2];
        cout<<(ans&1)<<"\n";
    }
    else cout<<ma-mi-r[2]<<"\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;

    while (t --) {
        solve();
    }
}