#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
using namespace std;

const int N=1e7+10;
int sum[N],vis[N],v[N<<1],l[N<<1],a[N],fail[N];
vector<pii> p;
string str;

void solve() {
	cin>>str; int n=str.size(); str=" "+str+" ";
	int sum0=0,sum1=0,m=0; p.clear();
	for (int i=1;i<=n;i++) {
		if (str[i]=='0') ++sum0;
		else ++sum1;
	}
	if (!sum0||!sum1) {cout<<1<<'\n';return ;}
	if (sum1<sum0) {
		for (int i=1;i<=n;i++) {
			if (str[i]=='0') str[i]='1';
			else str[i]='0';
		} reverse(str.begin(),str.end());
	}
	for (int i=2,j=1;i<=n+1;i++) {
		if (str[i]==str[i-1]) ++j;
		else if (str[i-1]=='0') v[++m]=-j,j=1;
		else v[++m]=j,j=1;
	}
	// for (int i=1;i<=m;i++) cout<<v[i]<<' '; cout<<'\n';
	if (str[1]==str[n]) v[1]+=v[m],--m;
	int mn=0x3f3f3f3f,s;
	for (int i=1;i<=m;i++) {
		sum[i]=sum[i-1]+v[i];
		if (mn>=sum[i]) mn=sum[i],s=i;
	}
	for (int i=1;i<=m;i++) v[i+m]=v[i];
	// for (int i=s+1;i<=s+m;i++) cout<<v[i]<<' '; cout<<'\n';
	l[s+1]=1;
	for (int i=s+2;i<=s+m;i++)
		l[i]=l[i-1]+abs(v[i-1]);
	int ans=0;
	vector<pii> t;
	for (int i=s+m,s0=0;i>=s+1;i-=2) {
		v[i]+=1,v[i-1]-=1;
		s0+=-v[i]; t.pb({l[i],-v[i]});
		if (s0>v[i-1]) {
			int cnt=0,x=v[i-1];
			for (auto it=t.rbegin();it!=t.rend();it++) {
				int &l=it->fi,&d=it->se;
				if (d>=x) {l=l+x;d-=x;if (d==0) ++cnt;break;}
				++cnt;
			}
			while (cnt--) t.pop_back();
			s0-=v[i-1];
		}
		else {
			int L=l[i-1]+v[i-1]-s0;
			if (v[i-1]-s0!=0) p.pb({l[i-1],v[i-1]-s0+1});
			ans=max((t[0].fi+t[0].se-L)/2,ans); s0=0; t.clear();
		}
	}
//	cout<<ans<<'\n';
	if (p.empty()) {cout<<ans+1<<'\n'; return ;}
	for (auto [l,d]:p) {
		// cout<<l<<' '<<d<<'\n';
		for (int i=1,j=(l+ans-1)%n+1;i<=d;i++,j=j%n+1) a[j]=1;
	}
	for (int i=1;!vis[i];) {
		if (a[i]==1) {
			int j; vis[i]=1;
			for (i=i+1,j=0;a[i]!=1;i=i%n+1,j^=1) a[i]=j,vis[i]=1;
		}
		else ++i;
	}
	// for (int i=1;i<=n;i++) cout<<a[i]; cout<<'\n';
	
	fail[1]=0;
	for (int i=2,j=0;i<=n;i++) {
		while (j!=0&&a[i]!=a[j+1]) j=fail[j];
		if (a[i]==a[j+1]) ++j;
		fail[i]=j;
	}
	// for (int i=1;i<=n;i++) cout<<fail[i]<<' '; cout<<'\n';

	if (n%(n-fail[n])==0) ans+=n-fail[n];
	else ans+=n;
	cout<<ans<<'\n';
	for (int i=1;i<=n;i++) a[i]=0,vis[i]=0;
}

// 1111011100111100
// 0111101101011101
// 1011110110101110

// 3 -> 2, - 1

// 2 +
// 0001111
// 0010111

// - 2

// 7 +
// 0101011
// 1010101
// 1101010
// 0110101

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin>>T; while (T--) solve();
}