#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
using namespace std;

using ll = long long;
using ull = unsigned long long;

#define LOG(f...) fprintf(stderr, f)
#define DBG(f...) printf("%3d: ", __LINE__), printf(f)
// #define DBG(f...) void()
#define all(cont) begin(cont), end(cont)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

template <class T> void read(T &x) {
  char ch; x = 0;
  int f = 1;
  while (isspace(ch = getchar()));
  if (ch == '-') ch = getchar(), f = -1;
  do x = x * 10 + (ch - '0'); while (isdigit(ch = getchar()));
  x *= f;
}
template <class T, class ...A> void read(T &x, A&... args) { read(x); read(args...); }

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  int T;
  read(T);
  while (T--) {
    static char s[1000005];
    scanf("%s", s);
    int n = strlen(s);
    int c0 = count(s, s + n, '0'), c1 = n - c0;
    if (c0 > c1) {
      swap(c0, c1);
      for (int i = 0; i < n; ++i)
        s[i] ^= 1;
    }
    if (c1 == n) { puts("1"); continue; }
    if (s[0] != '0' || s[n - 1] != '1') {
      for (int i = 1; i < n; ++i)
        if (s[i - 1] == '1' && s[i] == '0') {
          rotate(s, s + i, s + n);
          break;
        }
    }
    vector<int> pos_1;
    for (int i = n - 1; i != -1; --i)
      if (s[i] == '1') pos_1.push_back(i);

    int stretch_0 = 0, mx_move = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] == '0') {
        if (stretch_0 & 1) {
          while (!pos_1.empty() && pos_1.back() < i)
            pos_1.pop_back();
          assert(!pos_1.empty());
          swap(s[i], s[pos_1.back()]);
          mx_move = max(mx_move, pos_1.back() - i);
          pos_1.pop_back();
        }
        ++stretch_0;
      }
      else stretch_0 = 0;
    }

    vector<int> fa(n);
    fa[0] = -1;
    for (int i = 1, j = -1; i < n; ++i) {
      while (j != -1 && s[j + 1] != s[i]) j = fa[j];
      j += s[j + 1] == s[i];
      fa[i] = j;
    }
    int per = n - (fa[n - 1] + 1);
    if (per != 0 && n % per == 0)
      printf("%d\n", mx_move + per);
    else
      printf("%d\n", mx_move + n);
  }
  return 0;
}