#include <bits/stdc++.h>

using namespace std;
const int N = 1e7 + 10;

int pos[3 * N], a[2 * N], T, ans, cnt[2], d[2 * N], Next[N], s[N], f[2 * N];
char str[N];

int valid(int l, int r)
{
    int s = 0;
    for(int i = r; i >= l; i--)
    {
        if(a[i] == 1) s++;
        else s--;
        if(s < 0) return 0;
    }
    return 1;
}

int main()
{
    //freopen("data.in", "r", stdin);
    scanf("%d", &T);
    while(T--)
    {
        ans = 0;
        cnt[0] = cnt[1] = 0;
        scanf("%s", str + 1);
        int n = strlen(str + 1);
        for(int i = 1; i <= 2 * n; i++) d[i] = 0;
        for(int i = 0; i <= 3 * n; i++) pos[i] = -1;
        for(int i = 1; i <= n; i++)
        {
            a[i] = str[i] - '0';
            cnt[a[i]]++;
        }
        if(cnt[0] < cnt[1])
        {
            for(int i = 1; i <= n; i++) a[i] ^= 1;
            reverse(a + 1, a + n + 1);
        }
        for(int i = 1; i <= n; i++) a[i + n] = a[i];
        for(int i = 1, s = 0; i <= 2 * n; i++)
        {
            int x = a[i] == 1 ? 1 : -1;
            s += x;
            f[i] = max(f[i - 1] + x, x);
            ans = max(ans, f[i] - 1);
            if(a[i] == 1 && i > n)
            {
                int len = i - pos[s + n];
                d[i - len + 1]++, d[i + 1]--;
            }
            pos[s + n] = i;
        }

        for(int i = 1; i <= 2 * n; i++) d[i] += d[i - 1];
        for(int i = 1; i <= n; i++) d[i] += d[i + n];
        for(int i = 1; i <= n; i++) d[i + n] = d[i];
        int flag = 0;
        for(int st = 1; st <= n && !flag; st++)
        {
            if(!d[st])
            {
                flag = 1;
                for(int i = st; i <= st + n - 1; i++)
                {
                    if(!d[i])
                    {
                        s[i - st + 1] = 0;
                    }
                    else
                    {
                        int j = i;
                        while(j < st + n - 1 && d[j + 1]) j++;
                        for(int k = i, c = 0; k <= j; k++, c ^= 1)
                        {
                            s[k - st + 1] = c;
                        }
                        i = j;
                    }
                }
            }
        }
        if(!flag)
        {
            for(int i = 1, c = 0; i <= n; i++, c ^= 1)
            {
                s[i] = c;
            }
        }
        for(int i = 2, j = 0; i <= n; i++)
        {
            while(j && s[j + 1] != s[i]) j = Next[j];
            if(s[j + 1] == s[i]) j++;
            Next[i] = j;
        }
        int t = (n % (n - Next[n])) ? n : n - Next[n];
        ans += t;
        printf("%d\n", ans);
    }
    return 0;
}