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

#define ll long long 
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>

#define N 100010
#define K 20

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        string s; cin >> s;
        int n = s.length();

        int c[3] { 0, 0, 0 };
        for (int i = 0; i < n; ++ i) {
            int x = s[i] - '0';
            if (x != 2) x ^= i & 1;
            c[x] ++;
        }

        if (c[2] >= abs(c[0] - c[1])) {
            cout << (c[2] - abs(c[0] - c[1])) % 2 << '\n';
        } else {
            cout << abs(c[0] - c[1]) - c[2] << '\n';
        }
    }
}