#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
#define isz(v) (int)(v.size())
using namespace std;

const int maxn=1000005;
const int inf=0x3f3f3f3f;

namespace Solve {
	int n;
	int a[maxn];
	int t[maxn];
	int c[maxn];
	int res[maxn];
	int fail[maxn];
	void clear() {
		fill(c+1,c+n+1,0);
		fill(res+1,res+n+1,0);
		fill(fail+1,fail+n+1,0);
	}
	void deal(int p) {
		int cnt=0;
		for(int i=p+1;i<=n;i++) {
			t[++cnt]=a[i];
		}
		for(int i=1;i<=p;i++) {
			t[++cnt]=a[i];
		}
		for(int i=1;i<=n;i++) {
			a[i]=t[i];
		}
	}
	void main(int tid) {
		string s;
		cin>>s;
		n=isz(s);
		for(int i=1;i<=n;i++) {
			a[i]=s[i-1]-'0';
		}
		int cc=accumulate(a+1,a+n+1,0);
		if(!cc||cc==n) {
			cout<<"1\n";
			return ;
		}
		if(cc>=n-cc) {
			for(int i=1;i<=n;i++) {
				a[i]^=1;
			}
			reverse(a+1,a+n+1);
		}
		int sum=0,mi=inf,pos=0;
		for(int i=n;i>=1;i--) {
			sum+=!a[i]?1:-1;
			if(sum<mi) {
				mi=sum;
				pos=i;
			}
		}
		if(pos) {
			deal(pos-1);
		}
		// for(int i=1;i<=n;i++) {
		// 	cerr<<a[i]<<" ";
		// }
		// cerr<<"\n";
		sum=0,pos=0;
		for(int i=n;i>=1;i--) {
			sum+=!a[i]?1:-1;
			if(!sum) {
				pos=i;
			}
		}
		if(pos) {
			deal(pos-1);
		}
		// for(int i=1;i<=n;i++) {
		// 	cerr<<a[i]<<" ";
		// }
		// cerr<<"\n";
		int cnt=0,p=0;
		++cnt;
		while(a[c[cnt]+1]) {
			c[cnt]++;
		}
		for(int i=1;i<=n;i++) {
			if(!a[i]) {
				if(p) {
					++cnt;
					for(int j=p+1;j<=i;j++) {
						c[cnt]+=a[j];
					}
				}
				p=i;
			}
		}
		int e=0;
		while(!c[e+1]) {
			e++;
		}
		// for(int i=1;i<=cnt;i++) {
		// 	cerr<<c[i]<<" ";
		// }
		// cerr<<"\n";
		int ans=0;
		while(*max_element(c+1,c+cnt+1)>1) {
			for(int i=1;i<=cnt;i++) {
				if(c[i]) {
					int j=i;
					while(j<=cnt&&c[j]) {
						j++;
					}
					j--;
					c[j]--;
					c[i-1]++;
					i=j;
				}
			}
			// cerr<<"c: ";
			// for(int i=1;i<=cnt;i++) {
			// 	cerr<<c[i]<<" ";
			// }
			// cerr<<"\n";
			ans++;
		}
		for(int i=cnt-ans+1+e;i<=cnt;i++) {
			c[i]++;
		}
		int cur=0;
		for(int i=1;i<=cnt;i++) {
			while(c[i]--) {
				res[++cur]=1;
			}
			res[++cur]=0;
		}
		// cerr<<ans<<"\n";
		// for(int i=1;i<=n;i++) {
		// 	cerr<<res[i]<<" ";
		// }
		// cerr<<"\n";
		int j=0;
		for(int i=2;i<=n;i++) {
			while(j&&res[i]!=res[j+1]) {
				j=fail[j];
			}
			if(res[i]==res[j+1]) {
				j++;
			}
			fail[i]=j;
		}
		if(n%(n-fail[n])==0) {
			ans+=n-fail[n];
		} else {
			ans+=n;
		}
		cout<<ans<<"\n";
	}
	void init() {
		
	}
}

signed main() {
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	Solve::init();
	for(int t=1;t<=T;t++) {
		Solve::main(t);
		Solve::clear();
	}
#ifndef ONLINE_JUDGE
	cerr<<"Time: "<<(1.0*clock()/CLOCKS_PER_SEC)*1000<<"ms\n";
#endif
}