#include <bits/stdc++.h>

using namespace std;

ifstream fin("prefix.in");
ofstream fout("prefix.out");

int main() {
    int t; fin >> t;

    while (t--) {
        string s; fin >> s;
        int n = (int)s.size();
        vector < int > phi(n, 0), per(n, -1);
        
        int idx = 0;
        for (int i = 1; i < n; ++i) {
            while (idx && s[i] != s[idx]) {
                idx = phi[idx - 1];
            }
            if (s[i] == s[idx]) {
                ++idx;
                phi[i] = idx;
            }
        }
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (phi[i] == 0) continue;
            if (phi[i] == i) {
                per[i] = i;
                ans = i + 1;
            } else if (phi[i] * 2 == i + 1) {
                per[i] = phi[i];
                ans = i + 1;
            } else if (per[phi[i] - 1] > -1 && phi[i] + per[phi[i] - 1] == i + 1) {
                per[i] = per[phi[i] - 1];
                ans = i + 1;
            }
        }
        fout << ans << "\n";
    }
    return 0;
}