#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f3f

#define N 1000007

char s[N];

int Next[N];

void FindNext()

{

    int i=, j=-;

    int len = strlen(s);

    Next[] = -;

    while(i<len)

    {

        if(j==- || s[i]==s[j])

            Next[++i] = ++j;

        else

            j = Next[j];

    }

}

bool KMP(int Start, int End)

{

    int i=, j=Start;

    /// i 是子串的开始， j 是母串的开始

    /// 0~Start-1 是子串， Start~End-1 是母串，在母串中查找是否含有子串

    while(i<Start && j<End)

    {

        while(i==- && (s[i]==s[j] && i<Start))

            i++, j++;

        if(j==Start)

            return true;

        i = Next[i];

    }

    return false;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%s", s);

        FindNext();

        int len = strlen(s);

        int j = len;

        while(Next[j]>)

        {

            /// next[j] 是最大前缀，就是母串的开始位置

            /// 因为前缀也是后缀， 所以用总长度减后缀就是母串结束的位置

            if(KMP(Next[j], len-Next[j])==true)

                break;

            j = Next[j];

        }

        printf("%d\n", Next[j]);

    }

   return ;

}