#pragma GCC optimize("-Ofast","-ffast-math","-funroll-all-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pl pair<ll, ll>
#define db double
#define mp make_pair
#define pb push_back
#define fi first
#define vi vector<int>
#define se second
#define mod 998244353
const int maxn = 10000005;
char s[maxn];
int cur[maxn];

template <typename T> bool chkmin(T &a, T b) {
    return (b < a) ? (a = b, 1) : 0;
}

template <typename T> bool chkmax(T &a, T b) {
    return (b > a) ? (a = b, 1) : 0;
}
int fl[maxn];
pair<int, vi> work(vi cur) {
    int s = cur.size();
    
    vi h;
    h.clear();
    h.reserve(s);
    int le = 0;
    int t = 0;
    for (int j = 0; j < s; j++) {
        h.pb(j);
        for (int m = 0; m < cur[j]; m++) {
            while (h.size()) h.pop_back();
        }
        if (h.size()) chkmax(t, j - h[0] + 1);
    }
    // j ~ t + 1 ~ j
    vi zrs(s);
    for (int i = 0; i <= s; i++) fl[i] = 0;
    h.clear();
    h.reserve(s);
    int tot = 0;
    for (int j = 0; j < s; j++) {
        h.pb(j); 
        fl[j] = 1;
        for (int m = 0; m < cur[j]; m++) {
            while (h.size()) {
                fl[h.back()] = 0;
                h.pop_back();
            }
        }
        if (fl[j]) tot += 1;
        if (j >= t && fl[j - t]) tot -= 1;
        assert(tot == h.size());
        zrs[j] = tot;
    }
    vi res(s);
    for (int j = 0; j < s; j++) {
        res[j] = cur[j] + zrs[j];
        if (j) res[j] -= zrs[j - 1];
    }
    return mp(t, res);
}
int solve() {
    scanf("%s", s);
    int n = strlen(s);
    int cnt[2] = {0, 0};
    for (int i = 0; i < n; i++)
        cnt[s[i] - '0'] += 1, 
        cur[i] = s[i] - '0';
    if (cnt[1] > cnt[0]) {
        for (int i = 0; i < n; i++)
            s[i] = '0' + '1' - s[i], 
            cur[i] ^= 1;
        swap(cnt[0], cnt[1]);
    }
    if (!cnt[1]) return 1;
    vi srt;
    for (int i = 0; i < n; i++) {
        if (cur[i]) {
            int len = 0;
            for (int j = i; j < i + n; j++) {
                if (cur[j % n]) {
                    if (j != i) {
                        srt.pb(len);
                        len = 0;
                    }
                }
                else len += 1;
            }
            srt.pb(len);
            break;
        }
    }
    
    auto period = [&](vi lens) {
        int id = 0;
        for (auto v : lens) {
            cur[id++] = 1;
            for (int j = 0; j < v; j++)
                cur[id++] = 0;
        }
        assert(id == n);
        for (int per = 1; per <= n; per++) {
            if (n % per != 0) continue;
            if (per == n) return n;
            int flag = 1;
            for (int u = 0; u < per; u++) {
                if (cur[u] != cur[u + per]) {
                    flag = 0;
                    break;
                }
            }
            if (flag) return per;
        }
        return 0;
    };
    int flag = 1;
    for (auto v : srt)
        if (v == 0) flag = 0;
    if (flag) return period(srt);

    int s = srt.size();
    int mxid = 0;
    int sum = 0;
    int mxsum = -1e9;
    for (int i = 0; i < s; i++) {
        sum += srt[i] - 1;
        if (chkmax(mxsum, sum)) mxid = i;
    }
    vi nw; nw.reserve(s);
    for (int j = mxid + 1; j < mxid + 1 + s; j++)
        nw.pb(srt[j % s]);
    auto res = work(nw);
    return res.fi + period(res.se);
}
int main() {
    int t; cin>>t;
    while (t--) {
        int ans = solve();
        printf("%d\n", ans);
    }
    return 0;
}
/*
3
1
001001
0001111
*/