#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int LMAX = 1000000;

int l;
int p[LMAX + 5], ciur[LMAX + 5];
char s[LMAX + 5];
vector<int> prime;

void calc_ciur() {
  for(int nr = 2; nr <= LMAX; nr++) {
    if(ciur[nr] == 0) {
      ciur[nr] = nr;
      prime.push_back(nr);
    }
    for(int i = 0; i < prime.size() && prime[i] <= ciur[nr] && prime[i] * nr <= LMAX; i++)
      ciur[prime[i] * nr] = prime[i];
  }
}

void kmp() {
  p[1] = 0;
  for(int i = 2; i <= l; i++) {
    int crt = p[i - 1];
    while(crt > 0 && s[i] != s[crt + 1])
      crt = p[crt];

    p[i] = crt;
    if(s[i] == s[crt + 1])
      p[i]++;
  }
}

int main() {
  freopen("prefix.in", "r", stdin);
  freopen("prefix.out", "w", stdout);
  int t;

  calc_ciur();

  scanf("%d ", &t);
  while(t--) {
    scanf("%s", s + 1);
    l = strlen(s + 1);

    kmp();
    int longest_p;
    for(longest_p = l; longest_p > 0; longest_p--) {
      int t = longest_p - p[longest_p];
      if(t != longest_p && longest_p % t == 0)
        break;
    }

    printf("%d\n", longest_p);
  }

  return 0;
}