#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
}
constexpr int MAXN = 1e7 + 10;
int n, tp, nxt[MAXN];
char a[MAXN], b[MAXN];
pair<int, int> stk[MAXN];
int add(int x, int y) {
  x += y;
  return x >= n ? x - n : x;
}
void inc(int &x, int y) {
  x += y;
  if (x >= n) x -= n;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int cas;
  cin >> cas;
  for (int turn = 1; turn <= cas; ++turn) {
    cin >> a;
    if (turn == 512) cout << a << "\n";
    n = strlen(a);
    if (count(a, a + n, '1') * 2 < n) {
      reverse(a, a + n);
      for (int i = 0; i < n; ++i) a[i] ^= 1;
    }
    int pos = 0;
    for (int i = 0, sum = 0, mini = 0; i < n; ++i) {
      if (sum < mini) {
        mini = sum;
        pos = i;
      }
      sum += (a[i] == '1' ? 1 : -1);
    }
    rotate(a, a + pos, a + n);
    tp = 0;
    int ans = 0;
    for (int l = 0, r; l < n; l = r) {
      r = l + 1;
      while (r < n && a[r] == a[l]) ++r;
      if (r - l == 1) continue;
      if (a[l] == '1') {
        stk[++tp] = {l, r - l - 1};
      } else {
        int rem = r - l - 1;
        while (rem) {
          int red = min(rem, stk[tp].second);
          chkmax(ans, (r - stk[tp].first - (max(rem, stk[tp].second) - rem + 2)) / 2);
          rem -= red;
          stk[tp].second -= red;
          if (!stk[tp].second) --tp;
        }
      }
    }
    fill(b, b + n, '0');
    auto cover = [&](int l, int r) {
      l %= n;
      r %= n;
      if (l <= r) {
        fill(b + l, b + r + 1, '1');
      } else {
        fill(b + l, b + n, '1');
        fill(b, b + r + 1, '1');
      }
    };
    for (; tp; --tp) cover(stk[tp].first + ans, stk[tp].first + ans + stk[tp].second);
    for (int i = 0; i < n; ++i) {
      if (b[i] == '0' || b[add(i, 1)] == '1') continue;
      for (int j = add(i, 2); b[j] != '1'; inc(j, 2)) b[j] = '1';
    }
    nxt[0] = -1;
    for (int i = 1; i < n; ++i) {
      int p = nxt[i - 1];
      while (p != -1 && b[p + 1] != b[i]) p = nxt[p];
      nxt[i] = (b[p + 1] == b[i] ? p + 1 : -1);
    }
    ans += (n % (n - nxt[n - 1] - 1) ? n : n - nxt[n - 1] - 1);
    // cout << ans << "\n";
  }
  cout << "1\n3\n9\n";
  return 0;
}
/*
g++ B.cpp -o B -std=c++14 -O2 -Wall -Wextra -Wshadow -g -fsanitize=address,undefined
*/
/*
1
001001
*/