#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define int long long
#define ld long double
#define i32 int
#define u32 unsigned int
#define i64 long long
#define u64 unsigned long long
#define u27 __int128
#define endl '\n'
#define VI vector<int>
#define VVI vector<VI>
#define rand() RANDOM(GEN)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define CTM (cout<<"Time:"<<static_cast<double>(clock()-START_TIME)/CLOCKS_PER_SEC*1000<<"ms"<<endl)
typedef long long ll;

using namespace std;
random_device SEED;
mt19937_64 GEN(SEED());
uniform_int_distribution<u64> RANDOM(0, numeric_limits<u64>::max());
const clock_t START_TIME = clock();

signed main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    IO;
    int tt;
    cin>>tt;
    while(tt--) {
        string x;
        cin>>x;
        int l=0,r=0,k=0;
        for(auto &c:x) {
            int p=c-'0';
            k=!k;
            if(p==2) l--,r++;
            else if((!p and k) or (p and !k)) l--,r--;
            else l++,r++;
        }
        int ans=1e18;
        for (int i = l; i <= r; ++i) {
            if(i%2==k) ans=min(ans,abs(i-0));
        }
        cout<<ans<<endl;
    }
    return 0;
}