#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl
const int N=2e5+10;

void solve()
{
    int n;
    string s;
    cin >> s;
    n = s.size();
    s = '|' + s;
    int dp[n + 5][2];
    rep(i, 0, n)
    {
        rep(j, 0, 1)
        {
            dp[i][j] = 1e9;
        }
    }
    dp[0][0] = 0;
    dp[0][1] = 0;
    rep(i, 1, n)
    {
        if(s[i] == '0' || s[i] == '2')
        {
            if(dp[i - 1][0])
            {
                dp[i][1] = min(dp[i][1], dp[i - 1][0] - 1);
            }
            else
            {
                dp[i][0] = min(dp[i][0], 1);
            }
            dp[i][0] = min(dp[i - 1][1] + 1, dp[i][0]);
        }
        if(s[i] == '1' || s[i] == '2')
        {
            if(dp[i - 1][1])
            {
                dp[i][0] = min(dp[i][0], dp[i - 1][1] - 1);
            }
            else
            {
                dp[i][1] = min(dp[i][1], 1);
            }
            dp[i][1] = min(dp[i - 1][0] + 1, dp[i][1]);
        }
    }
    cout << min(dp[n][0], dp[n][1]) << endl;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
// #ifndef  ONLINEJUDGE
//     freopen("test.in","r",stdin);
//     freopen("test.out","w",stdout);
// #endif
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}