#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define ull unsigned ll
#define ri register int
#define fo(i,x,y) for(ri i=(x);i<=(y);++i)
#define fu(i,x,y) for(ri i=(x);i<(y);++i)
#define fd(i,x,y) for(ri i=(x);i>=(y);--i)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e7+5;
int T,n,m,a[N],b[N],pi[N];
int cnt[2],pre[N],q[N];char str[N];
inline int W(ri x){
	if(x>=1&&x<=n)return x;
	if(x>n)return x-n;
	return x+n;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s",str+1);
		ri n=strlen(str+1);
		cnt[0]=cnt[1]=0;
		fo(i,1,n)++cnt[a[i]=str[i]-'0'];
		if(cnt[1]<cnt[0]){
			reverse(a+1,a+1+n);
			fo(i,1,n)a[i]^=1;
		}
		m=n<<1;
		fo(i,n+1,m)a[i]=a[i-n];
		fo(i,1,m){
			pre[i]=pre[i-1]+(a[i]?1:-1);
		}
		ri h=1,t=0,w=0;
		fo(i,1,n-1){
			while(h<=t&&pre[q[t]]>pre[i])--t;
			q[++t]=i;
		}
		fo(i,n,m){
			while(h<=t&&i-q[h]>=n)++h;
			while(h<=t&&pre[q[t]]>pre[i])--t;
			q[++t]=i;
			if(pre[q[h]]-pre[i-n]>=0){
				w=i;break;
			}
		}
		assert(w);
		w=w-n+1;m=0;
		ri s=0,la=1;
		fo(i,1,n)
			a[i]=a[i+w-1];
		fo(i,1,n){
			if(i==n||a[i]!=a[i+1]){
				b[++m]=i-la+1;la=i+1;
			}
		}
		for(ri i=1;i<m;i+=2){
			if(b[i]>1&&b[i+1]>1){
				s=max(s,min(b[i],b[i+1])-1);
			}
		}
		ri nw=0;
		fo(i,1,m){
			if(i&1){
				fo(j,1,b[i]){
					++nw;
					if(i<m&&b[i]>1&&b[i+1]>1){
						if(s>=j)a[W(nw-(s-j+1))]=1;
						else a[nw]=1;
					}
					else{
						a[W(nw-s)]=1;
					}
				}
			}
			else{
				fo(j,1,b[i]){
					++nw;
					if(b[i-1]>1&&b[i]>1){
						if(s>=b[i]-j+1)a[W(nw+(s-(b[i]-j+1)+1))]=0;
						else a[nw]=0;
					}
					else{
						a[W(nw+s)]=0;
					}
				}
			}
		}
		fo(i,2,n){
			ri j=pi[i-1];
			while(j&&a[j+1]!=a[i])j=pi[j];
			pi[i]=j+(a[j+1]==a[i]);
		}
		s+=n-pi[n];
		printf("%d\n",s);
	}
}