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

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

#define cin fin
#define cout fout
/*
*/
const int NMAX=1e6+5;
int n;
char s[NMAX];
int lps[NMAX];

void computeLPS()
{
    lps[0]=0;
    int len=0, i=1;
    while(i<n)
    {
        if(s[i]==s[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if(len!=0)
                len=lps[len-1];
            else
            {
                lps[i]=0;
                i++;
            }
        }
    }
    /*
    for(int i=0; i<n; i++)
        cout<<lps[i]<<" ";
    cout<<"\n";
    */
}

void solve()
{
    n=strlen(s);
    computeLPS();
    int i=1, j=0, len=1, best=0;
    while(i<n)
    {
        if(s[i]==s[j])
        {
            i++;
            j++;
            if(j==len)
            {
                best=i;
                j=0;
            }
        }
        else
        {
            if(j!=0)
                j=lps[j-1];
            else
                i++;
            len=i;
        }
    }
    cout<<best<<"\n";
}


int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        cin.get();
        cin>>s;
        solve();
    }

    return 0;
}