Cod sursa(job #724014)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("prefix.in");
ofstream fout("prefix.out");
#define dim 1000007
char v[dim];
int pi[dim],sol;
int n;
void read()
{
n=sol=0;
char c;
while((c=fin.get()) && (c!='\n') && (c!=EOF))
v[++n]=c;
}
void make_prefix()
{
int i, q=0;
for(i=2;i<=n;++i)
{
while(q!=0 && v[q+1]!=v[i])
q=pi[q];
if(v[q+1]==v[i])
++q;
pi[i]=q;
if(pi[i]>=0 && ((i+1)%(i-pi[i]))==0)
sol=i+1;
}
fout<<sol <<'\n';
}
int main()
{
int t;
fin>>t;fin.get();
for(;t;--t)
{
read();
make_prefix();
memset(pi,0,sizeof(pi));
}
return 0;
}