#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int T,n,a[N],b[N],c[N];
string s;
int prt[N],sum[N],r[N],ans[N],ans1[N],ansx[N];
int gd(int x,int y){return (y-x+c[0])%c[0];}
int gf(int x){if(x==prt[x])return x;return prt[x]=gf(prt[x]);}
int nxt[N];
int main()
{
	// freopen("1.in","r",stdin);
	scanf("%d",&T);
	int cntt=0;
	while(T--)
	{
		cin>>s,n=s.length(),s=' '+s;
		for(int i=1;i<=n;i++)a[i]=s[i]-'0';
		int cnt0=0,cnt1=0;
		for(int i=1;i<=n;i++)if(a[i])cnt1++;else cnt0++;
		if(cnt1>cnt0){for(int i=1;i<=n;i++)a[i]^=1;reverse(a+1,a+n+1);}
		b[0]=c[0]=0;
		for(int i=1;i<=n;i++)if(a[i]==0)
		{
			for(int j=i+1;j!=i;j=j%n+1)b[++b[0]]=a[j];
			b[++b[0]]=a[i];
		}
		int now=0;
		for(int i=1;i<=n;i++)
		{
			if(b[i])now++;
			else c[++c[0]]=now,now=0;
		}
		for(int i=1;i<=c[0];i++)prt[i]=i,sum[i]=c[i];
		// for(int i=1;i<=c[0];i++)printf("%d ",c[i]);printf("\n");
		vector<int>temp;
		for(int i=1;i<=c[0];i++)if(c[i])temp.push_back(i);
		int len=temp.size();
		queue<pair<int,int> >q;
		for(int i=0;i<len;i++)
		{
			int j=(i+1)%len;r[temp[i]]=temp[j]-1;
			// cout<<temp[i]<<" "<<temp[j]<<" "<<c[temp[i]]<<" "<<gd(temp[i],temp[j])<<endl;
			if(gd(temp[i],temp[j])<c[temp[i]])q.push({temp[i],temp[j]});
		}
		while(!q.empty())
		{
			int x=q.front().first,y=q.front().second;q.pop();
			x=gf(x),y=gf(y);if(x==y)continue;
			prt[y]=x,sum[x]+=sum[y],r[x]=max(r[x],r[y]);
			int j=gf(r[x]%c[0]+1);
			// cout<<x<<" "<<y<<" "<<j<<endl;
			if(j!=x && gd(x,j)<sum[x])q.push({x,j});
		}
		for(int i=1;i<=c[0];i++)ansx[i]=0;
		int ans=0;
		for(int i=0;i<len;i++)if(prt[temp[i]]==temp[i])
		{
			// cout<<temp[i]<<" "<<sum[temp[i]]<<endl;
			ans=max(ans,sum[temp[i]]-1);
			for(int j=temp[i];j<=temp[i]+sum[temp[i]]-1;j++)ansx[(j-1)%c[0]+1]=1;
		}
		// cout<<ans<<endl;
		// for(int i=1;i<=c[0];i++)printf("%d ",ansx[i]);printf("\n");
		int m=0;
		for(int i=1;i<=c[0];i++)
		{
			ans1[++m]=0;
			if(ansx[i])ans1[++m]=1;
		}
		// for(int i=1;i<=m;i++)printf("%d ",ans1[i]);printf("\n");
		for(int i=1;i<=n;i++)nxt[i]=0;
		for(int i=2;i<=n;i++)
		{
			nxt[i]=nxt[i-1];
			while(nxt[i] && ans1[nxt[i]+1]!=ans1[i])nxt[i]=nxt[nxt[i]];
			if(ans1[nxt[i]+1]==ans1[i])nxt[i]++;
		}
		int now1=nxt[n];
		while(n%(n-now1)!=0)now1=nxt[now1];
		ans+=n-now1;
		printf("%d\n",ans);
	}
	return 0;
}