#include <cassert>
#include <cstdio>
 
const int nmax=1000002;
int p[nmax];
char c[nmax];
 
int main()
{
    int t=0,i=0,sol=0,k=0;
 
    assert(freopen("prefix.in","r",stdin));
    assert(freopen("prefix.out","w",stdout));
 
    assert(scanf("%d\n",&t));
 
    for (t=t; t>0; --t)
    {
        gets(c+1);
 
        i=2;
        sol=0;
        k=0;
 
        int n;
        for (n= 1; c[n]!='\n'&& c[n]!=0; ++n){
        }
        --n;

        while (c[i]&&i<=n)
        {
            while (k>0 && c[i]!=c[k+1])
                k=p[k];
 
            if (c[i]==c[k+1])
                ++k;
 
            p[i]=k;
 
            ++i;
        }
 
        assert(printf("%d\n",sol));
    }
 
    return 0;
}