#include <bits/stdc++.h>

char b[1000001];
int pi[1000001];

int main() {
    FILE *fin, *fout;
    int n, m, i, j, c = 0, x, mx, d, pos, p, l, k;
    fin = fopen( "prefix.in", "r" );
    fout = fopen( "prefix.out", "w" );
    fscanf( fin, "%d", &n );
    fgetc( fin );
    for ( k = 0; k < n; k++ ) {
        m = 0;
        do {
            b[++m] = fgetc( fin );
        } while ( b[m] != '\n' );
        m--;
        j = 0;
        mx = 0;
        l = 0;
        for ( i = 2; i <= m; i++ ) {
            while ( j > 0 && b[i] != b[j + 1] )
                j = pi[j];
            x = i;
            d = 0;
            while ( i <= m && b[i] == b[j + 1] ) {
                j++;
                pi[i++] = j;
                d = 1;
            }
            if ( d == 1 )
                i--;
            if ( j >= x - 1 ) {
                mx = ( mx > j ? mx : j );
                p = i - mx;
                l = 0;
                while ( l + p <= i )
                    l += p;
            }
        }
        fprintf( fout, "%d\n", l );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}