#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
namespace Maths {
	const int mod = 998244353;
	int power(int x, int y) {
		int ans = 1; while (y) {
			if (y & 1) ans = 1ll * ans * x % mod; y >>= 1; x = 1ll * x * x % mod;
		} return ans;
	}
	int power(int x, int y, int mod) {
		int ans = 1; while (y) {
			if (y & 1) ans = 1ll * ans * x % mod; y >>= 1; x = 1ll * x * x % mod;
		} return ans;
	}
	int fac[1000010], inv[1000010];
	void init() {
		fac[0] = fac[1] = inv[0] = inv[1] = 1;
		for (int i = 2; i <= 1e6; i++) fac[i] = 1ll * fac[i - 1] * i % mod, inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
		for (int i = 2; i <= 1e6; i++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
	}
	int binom(int n, int m) {
		return n < m || m < 0 ? 0 : 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
	}
} using namespace Maths;
namespace Loser {
	int n, sum, s[10000010], b[10000010], a[10000010];
	struct seg {
		int l, r, b;
	}; stack<seg> st;
	int bor[10000010];
	int period(int* s) {
		for (int i = n; i >= 1; i--) s[i] = s[i - 1];
		bor[1] = 0;
		for (int i = 2; i <= n; i++) {
			bor[i] = bor[i - 1];
			while (bor[i] && s[bor[i] + 1] != s[i]) bor[i] = bor[bor[i]];
			if (s[bor[i] + 1] == s[i]) bor[i]++;
		}
//		cout<<"deb:"; for (int i=1;i<=n;i++)cout<<s[i];cout<<'\n';
		for (int x = bor[n]; x; x = bor[x]) {
			if (n % (n - x) == 0) return n - x;
		} return n;
	}
	char c[10000010];
	void debb(int*a){
//		cout<<"deb:";for(int i =0;i<n;i++)cout<<a[i];cout<<'\n';
	}
	void main() {
		cin >> c; n = strlen(c); sum = 0;
		for (int i = 0; i < n; i++) a[i] = c[i] ^ 48, sum += a[i];
		if (sum < n - sum) {
			for (int i = 0; i < n; i++) a[i] ^= 1; reverse(a, a + n), sum = n - sum;
		}
		int p = -1;
		for (int i = 0; i < n; i++) {
			s[i] = (i ? s[i - 1] : 0) + (a[i] ? 1 : -1); if ((p == -1 || s[i] < s[p]) && a[i] == 0) p = i;
		}
		for (int i = 0; i < n; i++) b[i] = a[(p + i + 1) % n]; 
		for (int i = 0; i < n; i++) swap(a[i], b[i]);
		debb(a);
		for (int i = 0; i < n; i++) {
			s[i] = (i ? s[i - 1] : 0) + (a[i] ? 1 : -1); assert(s[i]>=0);
		}
		/* ---------------------------- */
		int ans = 0;
		while (st.size()) st.pop();
		for (int i = 0, k; i < n; i++) {
			k = i; while (k + 1 < n && a[k + 1] == a[k]) ++k;
			if (k == i) continue;
			seg r = seg{i, k, a[k]}; i = k; 
			if (a[k]) {
				st.push(r);
			} else {
				while (st.size() && st.top().b) {
					seg l = st.top(); st.pop();
					int mid = (l.r + r.l) >> 1;
					int lenl = l.r - l.l + 1, lenr = r.r - r.l + 1;
					ans = max(ans, mid - l.r + min(lenl, lenr) - 1);
					if (lenl < lenr) {
						r.l += lenl - 1;
						if (r.l == r.r) break; 
					} else if (lenl > lenr) {
						r.r = 0; l.r -= lenr - 1; if (l.l != l.r) st.push(l); break;
					} else {
						r.r = 0; break;
					}
				}
				if (r.r > r.l) st.push(r);
			} 
		}
		/* ---------------------------- */
		for (int i = 0; i <= n; i++) b[i] = -1;
		bool flag = st.empty();
		int l=0,B;
		while (st.size()) {
			seg t = st.top(); st.pop();
//			deb(t.l),deb(t.r),deb(t.b)<<'\n';
			if(l)assert((l-t.r)%2==(t.b!=B)); l=t.l;B=t.b;
			for (int i = t.l; i <= t.r; i++) b[i] = t.b;
		}
//		debb(b); 
//		return;
		for (int i = 0; i < n; i++) {
			if (b[(i + 1) % n] == -1 && b[i] != -1) b[(i + 1) % n] = b[i] ^ 1; 
		}
		for (int i = 0; i < n; i++) {
			if (b[(i + 1) % n] == -1 && b[i] != -1) b[(i + 1) % n] = b[i] ^ 1; 
		}
		if (flag) {
			for (int i = 0; i < n; i++) b[i] = ~i & 1;
		}
		debb(b);deb(ans);
		cout << period(b) + ans << '\n';
	}
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1; cin >> T; while (T--) Loser::main(); return 0;
}