#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=0;sss=s;
        int n=s.length();
        for(int i=n/2;i<n;i++)
        {
            if(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++;
                }
            }
        }
        for(int i=1;i<n;i++)
        {
            if(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++;
                }
            }
        }
        ans=min(ans,(int)ss.size());
        // cerr<<s;
        s=sss;
        for(int i=1;i<n;i++)
        {
            if(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++;
                }
            }
        }
        for(auto i:s)
        {
            if(i!='4') ss=ss+i;
        }

        cout<<ss.size()<<"\n";
	}
	
	return 0;
}