#include <cstdio>

const int N = 1000010;

int n, per[N], pi[N];

char s[N];

void init() {
    for (n = 1; s[n]; ++ n);
    -- n;
}

void solve() {
    int q = 0, poz = 0;
    pi[1] = 0;
    per[1] = 1;

    for (int i = 2; i <= n; ++ i) {
        while(q && s[q + 1] != s[i])
            q = pi[q];
        if (s[q + 1] == s[i])
            ++ q;
        pi[i] = q;
        if (per[pi[i]] == i - pi[i]) {
            per[i] = i - pi[i];
            poz = i;
            continue;
        }
        per[i] = i;
    }

    printf("%d\n", poz);
}

int main() {
    int t;
    freopen("prefix.in", "r", stdin);
    freopen("prefix.out", "w", stdout);

    scanf("%d\n", &t);

    while (t --) {
        gets(s + 1);
        init();
        solve();
    }
    return 0;
}