#include <iostream>
#include <fstream>

using namespace std;

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

constexpr size_t LIM = 1000005;
int prefix[LIM], period[LIM];
int T, j, k, ans, len;
char str[LIM];

int main() {
    fin >> T;
    for (; T; --T) {
        fin >> str;

        prefix[0] = 0, period[0] = 1, k = 0;
        for (j = 1; str[j] != '\0'; ++j) {
            while (k > 0 && str[j] != str[k])
                k = prefix[k - 1];
            if (str[j] == str[k]) ++k;
            prefix[j] = k;

            if (k < (j + 2) / 2) period[j] = j + 1;
            else if (period[k - 1] != j - k + 1) period[j] = j + 1;
            else period[j] = period[k - 1];
        }

        len = j, ans = -1;
        for (j = 0; j < len; ++j)
            if (period[j] != j + 1) ans = j;

        fout << ans + 1 << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}