#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MAXN = 2e7 + 100;
int pref[MAXN];
vector<int> rel;

int md(int i, int n) {
    if (i >= n) return i - n;
    return i;
}

void solve() {
    string s;
    cin >> s;
    /**for (int i = 0; i < 20; ++i) {
        s.push_back('0' + rand() % 2);
    }*/
    int n = s.size();
    int bal = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0') --bal;
        else ++bal;
    }
    if (bal == n || bal == -n) {
        cout << "1\n";
        return;
    }
    if (s[0] != '0' || s.back() != '1') {
        int id = -1;
        for (int i = 1; i < n; ++i) {
            if (s[i - 1] == '1' && s[i] == '0') {
                id = i;
            }
        }
        string s1;
        for (int i = id; i < n; ++i) {
            s1.push_back(s[i]);
        }
        for (int i = 0; i < id; ++i) {
            s1.push_back(s[i]);
        }
        s = s1;
    }
    if (bal < 0) {
        reverse(s.begin(), s.end());
        for (auto& ch : s) {
            ch = '0' + '1' - ch;
        }
        bal = -bal;
    }
    rel.clear();
    for (int i = 0; i < 2 * n; ++i) {
        pref[i + 1] = pref[i] + (s[md(i, n)] == '0');
    }
    for (int i = 1; i < n; ++i) {
        if (s[i] == s[i - 1] && s[i] == '1') {
            rel.push_back(i);
        }
    }
    int start = 0;
    for (int i = n; i < 2 * n; ++i) {
        if (s[i - n] == '1' && s[md(i - 1, n)] == '1') {
            rel.push_back(i);
        } else if (s[i - n] == '0') {
            int k = 0;
            while (i + 1 < 2 * n && s[i + 1 - n] == '0') {
                ++k;
                ++i;
            }
            if (k == 0) continue;
            int ind = rel[rel.size() - k];
            k = pref[i] - pref[ind];
            start = max(start, k);
        }
    }

    if (s[0] != '1' || s.back() != '0') {
        int id = -1;
        for (int i = 1; i < n; ++i) {
            if (s[i - 1] == '0' && s[i] == '1') {
                id = i;
            }
        }
        string s1;
        for (int i = id; i < n; ++i) {
            s1.push_back(s[i]);
        }
        for (int i = 0; i < id; ++i) {
            s1.push_back(s[i]);
        }
        s = s1;
    }

    rel.clear();
    for (int i = 0; i < 2 * n; ++i) {
        pref[i + 1] = pref[i] + (s[md(i, n)] == '1');
    }
    for (int i = 2 * n - 1; i >= n; --i) {
        if (s[i - n] == '1') {
            rel.push_back(i);
        } else if (i != n && s[i - n] == '0' && s[i - 1 - n] == '0') {
            rel.push_back(i);
        }
    }
    string res;
    int lst = 0;
    int cur = 0;
    /// cerr << s << endl;
    if (false) {
        res = s;
    } else {
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == '0') ++cur;
            if (i != 0 && s[i] == '0' && s[i - 1] == '0') {
                rel.push_back(i);
                /// /// cerr << "add " << i << endl;
            } else if (s[i] == '1') {
                int go = pref[rel[rel.size() - start - 1]] - pref[i + 1];
                if (i == 3) {
                    /// cerr << go << endl;
                    /// cerr << rel[rel.size() - start] << endl;
                    /// cerr << pref[7] << " " << pref[i] << endl;
                }
                int k = 0;
                rel.push_back(i);
                /// /// cerr << "add " << i << endl;
                while (i > 0 && s[i - 1] == '1') {
                    ++k;
                    --i;
                    rel.push_back(i);
                    /// /// cerr << "add " << i << endl;
                }
                if (k + go - start > 0) {
                    res.push_back('0');
                    ++lst;
                    while (lst != cur) {
                        res.push_back('1');
                        res.push_back('0');
                        ++lst;
                    }
                    int len = k + go - start + 1;
                    while (len) {
                        res.push_back('1');
                        --len;
                    }
                }
            }
        }
        char lst = '0';
        if (!res.empty()) {
            lst = res.back();
        }
        while (res.size() < n) {
            res.push_back('0' + '1' - lst);
            lst = '0' + '1' - lst;
        }
        res.resize(n);
    }
    vector<int> pi(res.size());
    for (int i = 1; i < res.size(); ++i) {
        int j = pi[i - 1];
        while (j != -1 && res[j] != res[i])
            j = j == 0 ? -1 : pi[j - 1];
        pi[i] = j + 1;
    }
    /// cerr << "start: "<< start << " " << res << "\n";
    /// cerr << res.size() << " " << n << "\n";
    /**if (res.size() != s.size()) {
        cout << s << endl;
        exit(0);
    } else {
        return;
    }*/
    assert(res.size() == s.size());
    for (int i = res.size(); i > 0; i = pi[i - 1]) {
        if (res.size() % (res.size() - pi[i - 1]) == 0) {
            /// cerr << "!!!!!!!\n";
            cout << start + res.size() - pi[i - 1] << "\n";
            return;
        }
    }
    /// cerr << "!!!!!\n";
    cout << start + res.size() << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }

    return 0;
}