#include<bits/stdc++.h>
using namespace std;

const int MAXT=1e6,MAXN=1e7;

int T,n,ans;
string s;
int stk[MAXN+5],tp,tmp[MAXN+5],tot;
int A[MAXN+5],kmp[MAXN+5];

inline int nxt(int x) {return (x+1)*(x<n-1);}
inline int lst(int x) {return x-1+(!x)*n;}
inline int plu(int a,int b) {return a+b-(a+b>=n)*n;}
inline int sub(int a,int b) {return a-b+(a<b)*n;}

int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		cin>>s,n=s.length();
		if(n==1) {cout<<1<<endl;continue;}
		ans=tp=tot=0;
		for(int i=0;i<n;i++)
			if(s[lst(i)]=='1' && s[i]=='1') stk[++tp]=i;
			else if(s[i]=='0' && s[nxt(i)]=='0')
			{
				if(tp) ans=max(ans,((i-stk[tp--]+1)>>1));
				else tmp[++tot]=i;
			}
		reverse(tmp+1,tmp+tot+1);
		while(tp && tot) ans=max(ans,((n-stk[tp--]+tmp[tot--]+1)>>1));
		for(int i=0;i<n;i++) A[i]=-1;
		for(int i=1;i<=tp;i++) A[plu(stk[i],ans)]=1;
		for(int i=1;i<=tot;i++) A[sub(tmp[i],ans)]=0;
		if(!tp && !tot) {cout<<ans+2<<endl;continue;}
		for(int i=0;i<n;i++)
			if(A[i]==0)
			{
				bool v=0;
				for(int j=nxt(i);A[j]<0;j=nxt(j)) A[j]=v,v^=1;
			}
			else if(A[i]==1)
			{
				bool v=1;
				for(int j=lst(i);A[j]<0;j=lst(j)) A[j]=v,v^=1;
			}
		for(int i=1;i<n;i++)
		{
			kmp[i]=kmp[i-1];
			while(kmp[i] && A[kmp[i]]^A[i]) kmp[i]=kmp[kmp[i]-1];
			kmp[i]+=(A[kmp[i]]==A[i]);
		}
		cout<<ans+n-kmp[n-1]<<endl;
	}
	return 0;
}