#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=0, j=-1;
    int len = strlen(s);

    Next[0] = -1;

    while(i<len)
    {
        if(j==-1 || s[i]==s[j])
            Next[++i] = ++j;
        else
            j = Next[j];
    }
}

bool KMP(int Start, int End) 
{
    int i=0, j=Start;
    /// i 是子串的开始， j 是母串的开始
    /// 0~Start-1 是子串， Start~End-1 是母串，在母串中查找是否含有子串
    
    while(i<Start && j<End)
    {
        while(i==-1 && (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]>0)
        {
            /// next[j] 是最大前缀，就是母串的开始位置
            /// 因为前缀也是后缀， 所以用总长度减后缀就是母串结束的位置
            if(KMP(Next[j], len-Next[j])==true)
                break;
            j = Next[j];
        }

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