#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("prefix.in");
ofstream fout("prefix.out");
char sir[1000005];
int p[1000005];
int main()
{
    int t; fin >> t;
    while(t--)
    {
        int n;
        fin >> sir;
        n=strlen(sir);
        p[0]=p[1]=0;
        int j=0, ok=0, cat=0, poz=-1;
        for(int i=1; i<n; i++)
        {
            while(sir[i]!=sir[j] && j>0)
                      j=p[j];
            if(sir[i]==sir[j])
            {
                p[i]=j;
                j++;
                p[i]++;
                if(p[i]%(i-p[i]+1)==0 && p[i]>=(i-p[i]+1))  poz=i;
                p[i]--;
            }
        }
        fout <<poz+1 << "\n";

    }
    return 0;
}