#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int MAXN = 1000010;
char str[MAXN];
int len[MAXN], n, t;

void preprocess() {
    int i, j;
    for (len[1] = 0, i = 2, j = 0; i <= n; ++i) {
        while (j && str[j + 1] != str[i])
            j = len[j];
        if (str[j + 1] == str[i])
            len[i] = ++j;
        else
            len[i] = 0;
    }
}

int findLength() {
    int max = 0;
    for (int i = 1; i <= n; ++i) {
        int k = i - len[i];
        if (i / k == double(i) / k && max < i && len[i])
            max = i;
    }
    return max;
}

int main() {
    ifstream fin("prefix.in");
    ofstream fout("prefix.out");
    fin >> t;
    fin.get();
    for (int i = 0; i < t; ++i) {
        fin.getline(str + 1, MAXN);
        n = strlen(str + 1);
        preprocess();
        fout << findLength() << '\n';
    }
    return 0;
}