#include<bits/stdc++.h>
using namespace std;constexpr int S1=1<<20;
char buf1[S1],*l1,*r1;
#define getchar() ((l1==r1&&(r1=(l1=buf1)+fread(buf1,1,S1,stdin)),l1!=r1)?*l1++:EOF)
template<typename T=int>inline T read()
{
	T x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
constexpr int S2=1<<20;
char buf2[S2],*l2=buf2;
#define putchar(c) (l2==buf2+S2&&(fwrite(buf2,1,S2,stdout),l2=buf2),*l2++=(c))
int _st[22];
template<typename T>inline void write(T x)
{
	int tp=0;
	do
		_st[++tp]=x%10;
	while(x/=10);
	while(tp)
		putchar(_st[tp--]+'0');
	putchar('\n');
}
constexpr int MN=10000005;
int n,len[MN],pos[MN],tp,nxt[MN];
bool a[MN],b[MN];
inline void work()
{
	char c=getchar();
	while(c!='0'&&c!='1')
		c=getchar();
	n=0;
	while(c=='0'||c=='1')
	{
		b[++n]=c-'0';
		c=getchar();
	}
	int s=0;
	for(int i=1;i<=n;i++)
		if(b[i])
			s++;
		else
			s--;
	if(s==n||s==-n)
	{
		write(1);
		return;
	}
	if(s<0)
	{
		for(int i=1;i<=n;i++)
			b[i]^=1;
		reverse(b+1,b+n+1);
	}
	s=0;
	int mn=n+1,mp;
	for(int i=1;i<=n;i++)
	{
		if(b[i])
			s++;
		else
			s--;
		if(s<mn)
			mn=s,mp=i;
	}
	for(int i=mp%n+1,t=1;t<=n;t++,i=i%n+1)
		a[t]=b[i];
	// cerr<<"a: ";
	// for(int i=1;i<=n;i++)
	// 	cerr<<a[i];
	// cerr<<endl;
	int ans=tp=0;
	for(int i=1;i<=n;)
	{
		int j,k;
		for(j=i;a[j];j++);
		for(k=j;k<=n&&!a[k];k++);
		// cerr<<"ijk: "<<i<<' '<<j<<' '<<k<<endl;
		len[++tp]=j-i,pos[tp]=i;
		int x=k-j;
		while(len[tp]<x)
			x-=len[tp]-1,tp--;
		ans=max(ans,(k-1-pos[tp]-(len[tp]-x+1))/2);
		if(len[tp]==x)
			tp--;
		else
			len[tp]-=x-1;
		i=k;
	}
	// cerr<<"ans1: "<<ans<<endl;
	for(int i=1;i<=n;i++)
		a[i]=0;
	for(int i=1;i<=tp;i++)
		for(int j=0;j<len[i];j++)
			a[pos[i]+j]=1;
	for(int i=1;i<pos[1];i++)
		a[pos[1]-i]=~i&1;
	for(int i=2;i<=n;i++)
		if(!a[i])
			a[i]=!a[i-1];
	// cerr<<"a: ";
	// for(int i=1;i<=n;i++)
	// 	cerr<<a[i];
	// cerr<<endl;
	for(int i=2,j=0;i<=n;i++)
	{
		while(j&&a[i]!=a[j+1])
			j=nxt[j];
		j+=(a[i]==a[j+1]);
		nxt[i]=j;
	}
	for(int i=nxt[n];;i=nxt[i])
		if(n%(n-i)==0)
		{
			ans+=n-i;
			// cerr<<"ans2: "<<n-i<<endl;
			break;
		}
	write(ans);
}
int main()
{
	int T=read();
	while(T--)
		work();
	fwrite(buf2,1,l2-buf2,stdout);
	return 0;
}