#include <bits/stdc++.h>

inline int Main() {
    std::string s;
    std::cin >> s;
    int c0 = 0, c1 = 0;
    for (auto ch : s) ++(ch == '0' ? c0 : c1);
    if (c0 < c1) {
        std::reverse(s.begin(), s.end()), std::swap(c0, c1);
        for (auto &ch : s) ch ^= 1;
    }
    int n = s.size();
    std::vector<int> S(n + 1);
    for (int i = n - 1; i >= 0; --i) S[i] = S[i + 1] + (s[i] == '0' ? -1 : 1);
    std::vector<int> P(n);
    for (int i = 1; i < n; ++i) P[i] = S[P[i - 1]] > S[i] ? P[i - 1] : i;
    int Max = 0;
    std::string t;
    t.resize(n, '0');
    if (s[n - 1] == '1') Max = n - P[n - 1] - 1 + S[P[n - 1]] - 1 >> 1, t[(n - 1 + S[P[n - 1]] - 1) % n] = '1';
    int p1 = n - 1;
    for (int i = n - 2; i >= 0; --i) {
        if (s[i] == '1') {
            int M1 = S[0] - S[i + 1] + S[p1] - 1, p2 = P[i], M2 = S[p2] - S[i + 1] - 1;
            auto [Ma, pa] = std::max(std::make_pair(M1, p1), std::make_pair(M2, p2));
            t[(i + Ma) % n] = '1', Max = std::max(Max, (i + n - pa) % n + Ma >> 1);
        }
        p1 = S[p1] > S[i] ? p1 : i;
    }
    std::vector<int> Fail(n, -1);
    for (int i = 1; i < n; ++i) {
        int &j = Fail[i] = Fail[i - 1];
        while (j != -1 && t[j + 1] != t[i]) j = Fail[j];
        j += t[j + 1] == t[i];
    }
    for (int j = Fail[n - 1]; j != -1; j = Fail[j]) if (n % (n - 1 - j) == 0) return std::cout << Max + (n - 1 - j) << '\n', 0;
    std::cout << Max + n << '\n';
    return 0;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T, Ret = 0;
    std::cin >> T;
    while (T--) Ret |= Main();
    return Ret;
}