#include <bits/stdc++.h>

using i64 = long long;

void sol() {
    std::string s;
    std::cin >> s;

    int cnt = 0, cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '2') cnt2++;
        if (i % 2 == 0) {
            if (s[i] == '0') {
                cnt1++;
            } else if (s[i] == '1') {
                cnt++;
            }
        } else {
            if (s[i] == '0') {
                cnt++;
            } else if (s[i] == '1') {
                cnt1++;
            }
        }
    }
    if (cnt2 >= std::abs(cnt1 - cnt)) {
        std::cout << cnt2 % 2 << "\n";
        return;
    }
    std::cout << std::min(std::abs(cnt2 - std::abs(cnt1 - cnt)),std::abs(cnt1 - cnt) + cnt2 % 2) << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    while (_--) {
        sol();
    }

    return 0;
}