#include <iostream>

#define MAX_LEN 2000000

using namespace std;

FILE *fin, *fout;

char v[MAX_LEN * 2 + 1];
int vSize;
int ans[MAX_LEN];
int ansSize;
int longestPrefix[MAX_LEN * 2 + 1];
int l, r;
int size1, size2;

int readWord() {
  int wordSize;
  char ch;

  wordSize = 0;
  ch = fgetc(fin);
  while ( ch != '\n' && ch != EOF ) {
    v[vSize] = ch;
    vSize++;
    wordSize++;
    ch = fgetc(fin);
  }

  return wordSize;
}

int calcLen(int pos) {
  int i, ans;

  if ( r <= pos ) {
    l = r = pos;
    while ( r < vSize && v[r] == v[r - l] ) {
      r++;
      i++;
    }
    r--;

    ans = r - l + 1;
  } else {
    if ( longestPrefix[pos - l] < r - pos + 1 ) {
      ans = longestPrefix[pos - l];
    } else {
      l = pos;
      while ( r < vSize && v[r] == v[r - l] )
        r++;
      r--;
      ans = r - pos + 1;
    }
  }

  return ans;
}

int main() {
  fin = fopen("prefix.in", "r");
  fout = fopen("prefix.out", "w");

  int i, n, i2, ans;

  fscanf(fin, "%d ", &n);
  while ( n-- ) {
    vSize = 0;
    readWord();
    l = r = 0;
    ans = 0;
    longestPrefix[0] = longestPrefix[1] = 0;
    for ( i = 1; i < vSize; i++ ) {
      longestPrefix[i] = calcLen(i);
    }

    for ( i = 1; i <= vSize / 2 + 1; i++ ) {
      longestPrefix[0] = vSize;

      i2 = i;
      while ( i2 < vSize && longestPrefix[i2] >= i ) {
        i2 += i;
      }

      if ( i2 != i )
        ans = max(ans, i2);
    }

    fprintf(fout, "%d\n", ans);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}