#include<bits/stdc++.h>
using namespace std;
char s[11000000];
int o[11000000];
int minn[11000000];
int pos[11000000];
int minn2[11000000];
int pos2[11000000];
int uu[11000000];
int t[11000000];
int bd[11000000];
int cal(int n){
	bd[1]=0;
	for(int i=2;i<=n;i++){
		int j=bd[i-1];
		while(j&&t[i]!=t[j+1])j=bd[j];
		j+=(t[i]==t[j+1]);
		bd[i]=j;
    }
	int j=bd[n];
	while(1){
		if(n%(n-j)==0)return n-j;
		j=bd[j];
	}
}
int main(){
	int _;
	cin>>_;
	while(_--){
		scanf("%s",s+1);
		int n=strlen(s+1);
		int u=0;
		for(int i=1;i<=n;i++)u+=s[i]-'0';
		if(2*u>n){
			for(int i=1;i<=n;i++)s[i]='1'-s[i]+'0';
			for(int i=1;2*i<=n;i++)swap(s[i],s[n+1-i]);
		}
		for(int i=1;i<=n;i++)o[i]=o[i-1]+2*(s[i]-'0')-1;
		for(int i=1;i<=n;i++){
			if(o[i]<=minn[i-1]){
				minn[i]=o[i];
				pos[i]=i;
			}
			else{
				minn[i]=minn[i-1];
				pos[i]=pos[i-1];
			}
		}
		minn2[n]=o[n];
		pos2[n]=n;
		for(int i=n-1;i>=0;i--){
			if(o[i]<minn2[i+1]){
				minn2[i]=o[i];
				pos2[i]=i;
			}
			else{
				minn2[i]=minn2[i+1];
				pos2[i]=pos2[i+1];
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			if(s[i]=='1'){
				int qq=o[i-1]-minn[i-1];
				int qqq=o[n]-minn2[i-1]+o[i-1];
				if(qq>=qqq){
					ans=max(ans,(qq+i-1-pos[i-1])/2);
					uu[i]=qq;
				}
				else{
					ans=max(ans,(qqq+n+(i-1)-pos2[i-1])/2);
					uu[i]=qqq;
				}
		    }
		}
		for(int i=1;i<=n;i++){
			if(s[i]=='1')t[(i+uu[i]-ans-1+n)%n+1]=1;
		}
		ans+=cal(n);
		printf("%d\n",ans);
	}
	return 0;
}