#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 1000000
#define MAXPOWER 1<<20
//MAXPOWER=2^(log2(NMAX)+1)

FILE *fin, *fout;

char sir[MAXN+2];
//MAXN+2 pt '\0'  si '\n'
unsigned int lungime, pi[MAXN];

int binary_search_strlen( char *string ){
  int bit = MAXPOWER, length;
  for( length = MAXN + 1; bit > 0; bit >>= 1 )
    if( length - bit > 0 && string[length - bit] == '\0' )
      length -= bit;
  return length;
}

void calculam_pi(){
  int i, j = 0;
  pi[0] = 0;
  for( i = 1; i < lungime; i++ ){
    while( j > 0 && sir[j] != sir[i] )
      j = pi[j - 1];
    if( sir[j] == sir[i] )
      j++;
    pi[i] = j;
  }
}

int main(){
  fin = fopen( "prefix.in", "r" );
  fout = fopen( "prefix.out", "w" );
  unsigned int t, i, j, raspuns;
  fscanf( fin, "%u", &t );
  fgetc( fin );//citim '\n' de dupa t

  while( t-- ){
    fgets( sir, MAXN+2, fin );
    lungime = binary_search_strlen( sir )-1;
    //-1 pt ca fgets() pune si '\n' la final si '\0'

    calculam_pi();
    raspuns = 0;
    for( i = lungime - 1; i > 0; i-- )
      if( pi[i] > 0 && (i + 1) % (i + 1 - pi[i]) == 0 ){
        raspuns = i + 1;
        i = 1;
      }
    fprintf( fout, "%d\n", raspuns );
  }
  fclose( fin );
  fclose( fout );
    return 0;
}