#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 10000000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int T,length,ans,dque[N+1],top;
char c[N+1];
bool used[N+1];
string s;
int main()
{
	int cnt,minn,maxn,ps,d;
	bool op;
	T=read();
	while (T--)
	{
		cin>>s,cnt=length=top=maxn=minn=ps=0;
		for (int i=0;i<s.length();++i) cnt+=(s[i]=='0');
		if ((cnt<<1)>s.length())
		{
			reverse(s.begin(),s.end());
			for (int i=0;i<s.length();++i) s[i]^='0'^'1';
		}
		cnt=0;
		for (int i=0;i<s.length();++i)
		{
			if (s[i]=='0') cnt++;
			else cnt--;
			if (cnt<minn) minn=cnt,ps=i+1;
		}
		for (int i=ps;i<s.length();++i) c[++length]=s[i];
		for (int i=0;i<ps;++i) c[++length]=s[i];
		for (int i=1;i<=length;++i)
		{
			if (c[i]=='0') dque[++top]=i;
			else if (top) maxn=max(maxn,(i-dque[top])>>1),top--;
		}
		top=0;
		for (int i=1;i<=length;++i)
			if (c[i]=='0')
				dque[++top]=i;
		minn=inf;
		for (int i=1;i<=top;++i) minn=min(minn,dque[i]+length-((top+i)<<1));
		for (int i=top;i>=1;--i) minn=min(minn,dque[i]-(i<<1)),used[((minn+(i<<1))%length+length)%length]=1;
		d=length,ans=length;
		for (int i=2;i<=length;++i)
			if (d%i==0)
			{
				while (d%i==0) d/=i;
				op=1;
				for (int j=0;j<length;++j) op&=(used[j]==used[(j+length/i)%length]);
				if (op) ans/=i;
			}
		printf("%d\n",ans+maxn);
	}
	return 0;
}