#include <bits/stdc++.h>
using namespace std;

string s;
long long sp[1000555];
long long mod = 1e9 + 7, b = 31;
long long p[1000555];

int main() {
    ifstream cin("prefix.in");
    ofstream cout("prefix.out");

    int n;
    cin >> n;

    p[0] = 1;
    for (int i = 1; i <= 1000000; ++i) {
        p[i] = (p[i - 1] * b) % mod;
    }

    for (int h = 1; h <= n; ++h) {
        cin >> s;

        long long bb = 1, sm = 0;
        for (int i = 0; i < s.size(); ++i) {
            sm = (sm + 1LL*int(s[i]) * bb) % mod;
            bb = (1LL*bb * b) % mod;
            sp[i + 1] = sm;
        }

        int rez = 0;
        for (int j = s.size(); j >= 1; --j) {
            bool ok = true;

            for (int i = j - 1; i >= 1; --i) {
                if (j % i == 0) {
                    long long s1, s2;
                    s1 = (1LL * sp[j - i] * p[i]) % mod;
                    s2 = (sp[j] - sp[i] + mod) % mod;

                    if (s1 == s2) {
                        ok = false;
                        break;
                    }
                }
            }

            if (ok == false) {
                rez = j;
                break;
            }
        }

        cout << rez << "\n";
    }

    return 0;
}