#include<bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i,s,n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) begin(v),end(v)
using namespace std;
using ll = long long;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using vp=vector<pll>;
using vvp=vector<vp>;
using vs=vector<string>;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }
const ll INF=1LL<<60;

ll safe_mod(ll x,ll y){
    x%=y;
    if(x<0) x+=y;
    return x;
}

void solve(string s){
    ll n=s.size();
    if(s==string(n,s[0])){
        cout<<1<<endl;
        return;
    }
    {
        ll t=0;
        for(auto c:s){
            if(c=='1') t++;
            else t--;
        }
        if(t>0){
            reverse(all(s));
            for(auto &c:s){
                if(c=='1') c='0';
                else c='1';
            }
        }
    }
    vl a;
    rep(i,0,n)if(s[i]=='1'){
        a.emplace_back(i);
    }
    ll m=a.size();
    ll I=-1;
    {
        vl b=a;
        rep(i,0,m-1) b.emplace_back(b[i]+n);
        rep(i,0,2*m-1) b[i]-=2*i;
        vl lt(m),rt(m);
        rrep(i,0,m-1) lt[i]=max(lt[i+1],b[m-i-2]);
        rep(i,1,m) rt[i]=max(rt[i-1],b[m-i-2]);
        rep(i,0,m)if(max(lt[i],rt[i])<=b[i+m-1]) I=i;
    }
    assert(I>=0);
    {
        vl b(m);
        rep(i,0,m) b[i]=(a[(I+i)%m]-a[I]+n)%n;
        a=b;
    }
    vl y(m),t(m);
    rep(i,1,m){
        if(a[i]<=t[i-1]+y[i-1]+1){
            y[i]=y[i-1]+1;
            t[i]=t[i-1]+2;
        }
        else{
            y[i]=a[i];
            t[i]=0;
        }
    }
    ll tm=*max_element(all(t));
    s=string(n,'0');
    rep(i,0,m){
        ll x=safe_mod(y[i]-(tm-t[i]),n);
        s[x]='1';
    }
    ll per=-1;
    rep(p,1,n+1)if(n%p==0){
        bool B=true;
        rep(j,0,n){
            B&=(s[(p+j)%n]==s[j]);
            if(!B) break;
        }
        if(B){
            per=p;
            break;
        }
    }
    assert(per>0);
    cout<<tm+per<<endl;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    ll q;
    cin>>q;
    while(q--){
        string s;
        cin>>s;
        solve(s);
    }
}