#include <bits/stdc++.h>

using namespace std;

const int N = 1e7;

char a[N + 5];
int n, s[N + 5], pos;
pair<int, int> stk[N + 5];
int top, res;
int b[N + 5], nxt[N + 5], ans;

void solve() {
  scanf("%s", a + 1), n = strlen(a + 1); int c1 = 0;
  for (int i = 1; i <= n; ++i) a[i] ^= '0', c1 += a[i];
  if (c1 < n - c1) {
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) a[i] ^= 1;
  }
  pos = -1;
  for (int i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + (a[i] ? 1 : -1);
    if (pos == -1 || s[i - 1] < s[pos - 1]) pos = i;
  }
  rotate(a + 1, a + pos, a + n + 1), res = top = 0, fill_n(b + 1, n, 0);
  for (int l = 1, r; l <= n; l = r + 1) {
    for (r = l; r < n && a[r + 1] == a[l]; ++r);
    if (l == r) { if (a[l]) b[l] = 1; continue; }
    if (a[l]) stk[++top] = {l, r - l + 1};
    else {
      int len = r - l + 1;
      while (top && len > 1) {
        auto &[l1, len1] = stk[top];
        int c = min(len1 - 1, len - 1);
        len1 -= c, len -= c, res = max(res, (r - len - l1 - len1 + 1) / 2);
        if (len1 == 1) --top, b[l1] = 1;
      }
    }
  }
  for (int i = 1; i <= top; ++i) { auto &[l, len] = stk[i]; fill_n(b + l, len, 1); }
  for (int i = 1; i <= n; ++i) if (!b[i] && !b[i - 1]) b[i] = 1;
  for (int i = 2, j = 0; i <= n; ++i) {
    for (; j && b[j + 1] != b[i]; j = nxt[j]);
    if (b[j + 1] == b[i]) ++j;
    nxt[i] = j;
  }
  ans = res + n;
  if (!(n % (n - nxt[n]))) ans -= nxt[n];
  printf("%d\n", ans);
}

int T;

int main() {
  //freopen("game.in", "r", stdin), freopen("game.out", "w", stdout);
  for (scanf("%d", &T); T; --T) solve();
}