#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

constexpr int NMAX = 1e6 + 1;

string s,r;

int kmp()
{
    int n = s.size(); if(n == 2) return 0;
    vector<int> pi(n + 1,0); int j = 0;
    for(int i = 2; i < n ; i++)
        {
            while(j && s[i] != s[j + 1]) j = pi[j];
            if(s[i] == s[j + 1]) j++;
            pi[i] = j;
        }

    int p = 2,ans = 0;
    while(p < n)
        {
            if(pi[p] != 1)
                {
                    p++;
                    continue;
                }

            int op = p + 1; if(p == 2) ans = 2;
            while(op < n && pi[op] == (pi[op - 1] + 1))
                {
                    int lung = op - p + 1;
                    if(lung % (p - 1) == 0) ans = op;
                    op++;
                }

            p = op + 1;
        }

    return ans;

}

void solve()
{
    s = " "; cin >> r;
    s += r; cout << kmp() << '\n';
}

int main() {

    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);

    int t; cin >> t;
    while(t--) solve();

}