#include <cstdio>
#include <cstring>

using namespace std;

#define Nmax 1000001

char s[Nmax];
int T[Nmax];

int N, M;

void KMP(){

    int k = 0;

    for(int i = 2; i <= N; i++){

        while( k > 0 && s[k+1] != s[i] )
            k = T[k];

        if( s[k+1] == s[i] )
            k++;

        T[i] = k;
    }
}

int raspuns(){

    for(int i = N; i > 0; i--)
        if( T[i] && !( i % ( i - T[i] ) ) )
            return i;

    return 0;
}

void init(){

     N = strlen(s);

    for(int i = N; i >= 0; i--)
        s[i] = s[i-1];

    memset(T, 0, sizeof(T));
}

void rezolva(){

    freopen("prefix.in", "rt", stdin);
    freopen("prefix.out", "wt", stdout);

    scanf("%d", &M);

    for(; M; M--){

        scanf("%s", s);
        KMP();
        printf("%d\n", raspuns());
    }

    fclose(stdin);
    fclose(stdout);
}

int main(){

    rezolva();

    return 0;
}