#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 2e7 + 10;
const int INF = 1e9;
int n;
int a[N], b[N], f[N], nxt[N];
char buff[N];
void solve() {
  scanf("%s", buff + 1); n = strlen(buff + 1);
  for(int i = 1; i <= n; i++)a[i] = buff[i] - '0';
  int cnt = 0;
  for(int i = 1; i <= n; i++)cnt += a[i];
  if(cnt > n / 2) {
    for(int i = 1; i <= n; i++)a[i] ^= 1;
    reverse(a + 1, a + 1 + n);
  }
  int pos = 0, ans = 0;
  for(int i = 1; i <= n; i++)ans += (a[i] && a[i % n + 1]);
  for(int i = 1; i <= n; i++)a[i + n] = a[i];
  for(int i = 1, j = 0; i <= n * 2; i++) {
    if(!a[i])continue;
    if(!j || f[j] < i - j - 1)f[i] = 0;
    else f[i] = f[j] + 1;
    j = i; ans = max(ans, f[i]);
  }
  for(int i = 1; i <= n; i++)if(a[i + n] && !f[i + n]) {pos = i; break;}
  rotate(a + 1, a + pos, a + n + 1);
  cnt = 0;
  for(int i = 1; i <= n; i++) {
    if(a[i])cnt++;
    if(!b[i - 1] && cnt)b[i] = 1, cnt--;
    else b[i] = 0;
  }
  for(int i = 2, j = 0; i <= n; i++) {
    while(j && b[j + 1] != b[i])j = nxt[j];
    if(b[j + 1] == b[i])j++;
    nxt[i] = j;
  }
  int cur = nxt[n];
  while(n % (n - cur))cur = nxt[cur];
  ans += n - cur;
  printf("%d\n", ans);
  return ;
}
int main() {
  int test = read();
  while(test--)solve();
  return 0;
}