#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
 
const int N=2e5+10;
const int M=0x3f3f3f3f3f3f3f3f;
int a[N];


signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--)
	{
		string s,ss,sss;cin>>s;int ans=M;
        int n=s.length();
        // for(int i=0;i<n;i++)
        // {
        //     if(((s[i-1]!='0'||s[i-1]!='1')&&(s[i]!='0'||s[i]!='1'))&&s[i-1]==s[i]) 
        //     {
        //         int x=i-1,y=i;
        //         while(x>=0&&y<n)
        //         {
        //             if(s[x]==s[y]&&(s[x]=='0'||s[x]=='1')) s[x]='4',s[y]='4';
        //             else break;
        //             x--;y++;
        //             while(x>=0&&s[x]>'1') x--;
        //             while(y<=n&&s[y]>'1') y++;
        //         }
        //     }
        //     // cerr<<s<<"\n";
        // }
        // for(int i=0;i<n;i++) 
        // {
        //     if(s[i]!=4) sss=sss+s[i];
        // }
        // s=sss;
        // n=s.size();
        
        for(int i=0;i<n;i++)
        {
            if((s[i-1]!='4'&&s[i]!='4'&&(s[i-1]=='2'||s[i]=='2'))||s[i-1]==s[i]) 
            {
                int x=i-1,y=i;
                while(x>=0&&y<n)
                {
                    if(s[x]==s[y]&&s[x]!='4') s[x]='4',s[y]='4';
                    else if(s[x]=='2'||s[y]=='2') s[x]='4',s[y]='4';
                    else break;
                    x--;y++;
                    while(x>=0&&s[x]=='4') x--;
                    while(y<=n&&s[y]=='4') y++;
                }
            }
            // cerr<<s<<"\n";
        }
        int cnt=0;
        for(auto i:s)
        {
            if(i!='4') cnt++;
        }
        ans=min(ans,cnt);

        s=sss;
        for(int i=n-1;i>=1;i--)
        {
            if((s[i-1]!='4'&&s[i]!='4'&&(s[i-1]=='2'||s[i]=='2'))||s[i-1]==s[i]) 
            {
                int x=i-1,y=i;
                while(x>=0&&y<n)
                {
                    if(s[x]==s[y]&&s[x]!='4') s[x]='4',s[y]='4';
                    else if(s[x]=='2'||s[y]=='2') s[x]='4',s[y]='4';
                    else break;
                    x--;y++;
                    while(x>=0&&s[x]=='4') x--;
                    while(y<=n-1&&s[y]=='4') y++;
                }
            }
        }
        cnt=0;
        for(auto i:s)
        {
            if(i!='4') cnt++;
        }
        ans=min(ans,cnt);
        

        cout<<ans<<"\n";
	}
	
	return 0;
}