// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
// #define int long long
#define i64 long long
#define pii pair <int, int> 
using namespace std;
inline int read(void) {
    int x=0,sgn=1; char ch=getchar();
    while(ch<48||57<ch) {if(ch==45)sgn=0;ch=getchar();}
    while(47<ch&&ch<58) {x=x*10+ch-48;   ch=getchar();}
    return sgn? x:-x;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
/*
    write((Ans%p+p)%p); pls
*/
int n,cnt0,cnt1;
char s[10000007];
int pre[10000007],a[10000007],minpost;
int stk[10000007],top,pos[10000007],border[10000007];
inline void shift(void) {
    int m=0;
    for(int i=minpost+1; i<=n; ++i) a[++m]=s[i];
    for(int i=1; i<=minpost; ++i) a[++m]=s[i];
} 
inline int getperiod(void) {
    border[1]=0;
    for(int i=2; i<=n; ++i) {
        border[i]=border[i-1];
        while(border[i]&&s[i]!=s[border[i]+1]) border[i]=border[border[i]];
        if(s[i]==s[border[i]+1]) ++border[i];
    }
    int p=n-border[n];
    if(n%p) p=n;
    return p;
}
inline void work() {
    scanf("%s",s+1); n=strlen(s+1); cnt0=cnt1=top=0;
    for(int i=1; i<=n; ++i) {
        if((s[i]-='0')) ++cnt1;
        else ++cnt0;
    } 
    if(cnt0>cnt1) {
        reverse(s+1,s+n+1); 
        for(int i=1; i<=n; ++i) s[i]^=1;
    }
    minpost=0;
    for(int i=1; i<=n; ++i) if((pre[i]=pre[i-1]+(s[i]?1:-1))<pre[minpost]) minpost=i;
    shift();
    // cerr<<"shifted string : "; for(int i=1; i<=n; ++i) cerr<<(char)(a[i]+'0'); cerr<<endl;
    int cnt=-1,lst=1,mxt=0; a[n+1]=a[n]^1;
    for(int i=1; i<=n+1; ++i) {
        if(a[i]!=lst) {
            // cerr<<"r = "<<i-1<<' '<<cnt<<' '<<a[i-1]<<endl;
            if(cnt) {
                if(!a[i]) {
                    ++top;
                    stk[top]=cnt;
                    pos[top]=i;
                } else {
                    int l=i-cnt-1,curt=0;
                    while(cnt) {
                        assert((l^pos[top])%2==0);
                        curt+=(l-pos[top])/2;
                        l=pos[top];
                        // cerr<<l<<' '<<pos[top]<<' '<<stk[top]<<' '<<cnt<<" curt : "<<curt<<" added : "<<l-pos[top]<<endl;
                        if(stk[top]>cnt) {
                            stk[top]-=cnt;
                            pos[top]-=cnt;
                            curt+=cnt;
                            cnt=0;
                        } else {
                            cnt-=stk[top];
                            curt+=stk[top];
                            l-=stk[top];
                            --top;
                        }
                    }
                    mxt=max(mxt,curt);
                }
            }
            cnt=0;
            lst=a[i];
        } else ++cnt;
    }
    lst=1;
    ++top;
    stk[top]=-1;
    pos[top]=n+1;
    for(int t=1; t<=top; ++t) {
        int len=stk[t],r=pos[t];
        // cerr<<len<<' '<<r<<endl;
        for(int i=lst; i<r; ++i) s[i]=((i^lst)&1);
        for(int i=0; i<=len; ++i) s[r-1-i]=1;
        lst=r;
    }
    int p=getperiod();
    // cerr<<"cur time : "<<mxt<<endl;
    // for(int i=1; i<=n; ++i) cerr<<(char)(s[i]+'0'); cerr<<endl;
    // cerr<<"period : "<<p<<endl;
    // cerr<<endl;
    // assert(lst==n+1);
    write(mxt+p); puts("");
}
signed main() {
    // freopen("localinput","r",stdin);
    // freopen("localoutput","w",stdout);
    int T=read();
    while(T--) work();
    // fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
    return 0;
}