#include <bits/stdc++.h>

using namespace std;

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

int T;
char s[1001001];
int pi[1001001];

int main()
{
    fin >> T;
    fin.get();
    while(T--)
    {
        fin >> (s + 1);
        int j = 0, n = strlen(s + 1);
        int ans = 0, maxi = 0;
        for(int i = 2; i <= n; i ++)
        {
            while(s[i] != s[j + 1] && j != 0)
            {
                j = pi[j];
            }
            if(s[i] == s[j + 1])
            {
                j++;
            }
            pi[i] = j;
        }
        for(int i = 1; i <= n; i ++)
        {
            if(pi[i] > maxi)
            {
                maxi = pi[i];
                ans = i;
            }
        }
        fout << ans << '\n';
    }
}