#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

void solve()
{
    int n; string s; cin >> s; n = s.size(); s = " " + s;
    vector<int> a;
    for(int i = 1; i <= n; ++i) {
        if(a.size() && s[i] - '0' == a.back() && s[i] - '0' != 2) a.pop_back();
        else a.push_back(s[i] - '0');

        if(a.size() > 3) {
            int x = a[(int)a.size() - 1], y = a[(int)a.size() - 2], z = a[(int)a.size() - 3];
            if(y == 2 && ((x == 0 && z == 1) || (x == 1 && z == 0))) {
                a.pop_back(), a.pop_back(), a.pop_back(), a.push_back(2);
            }
        }
        // cout << "check: ";for(auto x:a) cout << x << " ";  cout << endl;
    }

    //0100202010
    //022010

    //0220101221

    vector<int> ans[2];
    int cnt[2];
    for(auto x:a) {
        if(!ans[0].size()) {
            ans[0].push_back(x);
        } else {
            if((x == ans[0].back() && x != 2) || (x != ans[0].back() && (x == 2 || ans[0].back() == 2) )) {
                ans[0].pop_back();
            } else {
                ans[0].push_back(x);
            }
        }
    }
    if(ans[0].size() && ans[0][0] == 2) { 
        cnt[0] = ans[0].size() % 2;
    } else {
        cnt[0] = ans[0].size();
    }

    int res = n;
    ans[0].clear();
    for(int i = 1; i < a.size(); ++i) {
        int x = a[i];
        if(!ans[0].size()) {
            ans[0].push_back(x);
        } else {
            if((x == ans[0].back() && x != 2) || (x != ans[0].back() && (x == 2 || ans[0].back() == 2) )) {
                ans[0].pop_back();
            } else {
                ans[0].push_back(x);
            }
        }
    }
    if (ans[0].size() != 0)
    {
        if (ans[0].size() && a[0] == ans[0][0]) res = min(res, (int)ans[0].size() - 1);
        else res = min(res, (int)ans[0].size());
    }

    reverse(a.begin(), a.end());
    for(auto x:a) {
        if(!ans[1].size()) {
            ans[1].push_back(x);
        } else {
            if((x == ans[1].back() && x != 2) || (x != ans[1].back() && (x == 2 || ans[1].back() == 2) )) {
                ans[1].pop_back();
            } else {
                ans[1].push_back(x);
            }
        }
    }

    if(ans[1].size() && ans[1][0] == 2) { 
        cnt[1] = ans[1].size() % 2;
    } else {
        cnt[1] = ans[1].size();
    }

    ans[1].clear();
    for(int i = 1; i < a.size(); i++) {
        int x = a[i];
        if(!ans[1].size()) {
            ans[1].push_back(x);
        } else {
            if((x == ans[1].back() && x != 2) || (x != ans[1].back() && (x == 2 || ans[1].back() == 2) )) {
                ans[1].pop_back();
            } else {
                ans[1].push_back(x);
            }
        }
    }
    if (ans[1].size() != 0)
    {
        if (ans[1].size() && a[1] == ans[1][0]) res = min(res, (int)ans[1].size() - 1);
        else res = min(res, (int)ans[1].size());
    }

    cout << min({cnt[0], cnt[1], res}) << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}