#include<bits/stdc++.h>
using namespace std;
int n;
char s[2000005],t[2000005];
int sum[2000005];
int num[1000005];
int nxt[1000005];
int main(){
	int _;scanf("%d",&_);
	while(_--){
		scanf("%s",s+1);n=strlen(s+1);
		{
			int cnt[2]={};
			for(int i=1;i<=n;i++)cnt[s[i]^'0']++;
			if(cnt[0]<cnt[1]){
				for(int i=1;i<=n;i++)s[i]^=1;
				reverse(s+1,s+n+1);
			}
		}
		int mx=0;
		for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(s[i]^'0')*2-1,mx=max(mx,sum[i]);
		for(int i=1;i<=n;i++)if(sum[i-1]==mx){
			for(int j=1;j<=n;j++)t[j]=s[j];
			for(int j=i;j<=n;j++)s[j-i+1]=t[j];
			for(int j=1;j<i;j++)s[n-i+1+j]=t[j];
			break;
		}
		for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(s[i]^'0')*2-1,assert(sum[i]<=0);
//		printf("s=%s\n",s+1);
		int len=0;
		for(int i=1,j=0;i<=n;i++)if(s[i]=='1'){
			if(sum[i-1]<=sum[j])j=i-1;
			num[i]=sum[i]-sum[j]-1;
			len=max(len,i-j-1);
		}
		for(int i=1;i<=n;i++)t[i]='0';
		for(int i=1;i<=n;i++)if(s[i]=='1')t[(i-(len-num[i])+n-1)%n+1]='1';
//		printf("len=%d\n",len);
//		printf("%s\n",t+1);
		for(int i=2,j=0;i<=n;i++){
			while(j&&t[j+1]!=t[i])j=nxt[j];
			if(t[j+1]==t[i])j++;
			nxt[i]=j;
		}
		printf("%d\n",len+n-nxt[n]);
	}
	return 0;
}