#include<string>
using namespace std;
#define MAX_N 1000003
#include<fstream.h>
ofstream g("prefix.out");
char s[MAX_N];
int N;
void solve()
{
    int i, L, nou, vechi;
    int sol=0;
    L=1;
    s[0]='!';
    N=strlen(s)-1;
    for(i=1;i<=N;++i)
    {
        if(s[i]==s[i-L])
        nou=vechi + 1;
        else
            {
            nou=0; L=i;
            }
        if(nou==L)
            {
                nou=0;
                sol=i;
            }
        vechi=nou;
    }
    g<<sol<<"\n";
}
int main()
{
    int T;
    ifstream f("prefix.in");
    f>>T;
    while(T--)
    {
        memset(s,0,sizeof(s));
        f.get(s,MAX_N);
        f.get();
        solve();
    }
    return 0;
}