HDU 6629

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int maxn=1e6+5;
int net[maxn];
char a[maxn];

void exkmp(char *a)
{
	int i=0,j,po,len=strlen(a);
	net[0]=len;
	while(i+1<len&&a[i]==a[i+1])
	{
		i++;
	}
	net[1]=i;
	po=1;
	for(i=2;i<len;i++)
	{
		if(net[i-po]+i<net[po]+po)
		{
			net[i]=net[i-po];
		}
		else
		{
			j=net[po]+po-i;
			if(j<0)
			{
				j=0;
			}
			while(i+j<len&&a[j]==a[j+i])
			{
				j++;
			}
			net[i]=j;
			po=i;
		}
	}
 } 
 
 int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",a);
		exkmp(a);
		long long sum=0;
		int len=strlen(a);
		for(int i=1;i<len;++i)
		{
			sum+=net[i];
			if(i+net[i]<len)
			{
				sum++;
			}
		}
		printf("%lld
",sum);
	}
	return 0;
}