# include <cstdio>
# include <cstring>

const char *FIN = "prefix.in", *FOU = "prefix.out" ;

char S[1000005] ;
int N, Q ;

int solve (void) {
    int sol = 0;
    S[0] = 1 ;
    for (int i = 1, j = strlen (S), k = 1, st = 0, dr = 0; i < j; ++i, st = dr) {
        if (S[i] == S[i - k] && (i == N || S[i + 1] == S[i - k + 1] || st + 1 == k)) dr = st + 1 ;
        else dr = 0, k = i ;
        if (dr == k) {
            dr = 0, sol = i ;
        }
    }
    return sol;
}

int main (void) {
    freopen (FIN, "r", stdin) ;
    freopen (FOU, "w", stdout) ;

    for (scanf ("%d", &Q) ; Q ; --Q) {
        scanf ("%s", S + 1) ;
        printf ("%d\n", solve ()) ;
    }
}