RT，本地能跑，洛谷IDE也能跑，蒟蒻自闭了

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rint register int
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
inline int rd() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return x*f;
}
const int N=1010;
int T,n,m;
char s[N];
int sa[N],height[N],x[N],y[N],t[N],rk[N];
void get_SA() {
	m=122;
	for(rint i=1;i<=n;++i)++t[x[i]=s[i]];
	for(rint i=1;i<=m;++i)t[i]+=t[i-1];
	for(rint i=n;i>=1;--i)sa[t[x[i]]--]=i;
	for(rint k=1;k<=n;k<<=1) {
		int num=0;
		for(rint i=n-k+1;i<=n;++i)y[++num]=i;
		for(rint i=1;i<=n;++i)if(sa[i]>k)y[++num]=sa[i]-k;
		for(rint i=1;i<=m;++i)t[i]=0;
		for(rint i=1;i<=n;++i)++t[x[i]];
		for(rint i=1;i<=m;++i)t[i]+=t[i-1];
		for(rint i=n;i>=1;--i)sa[t[x[y[i]]]--]=y[i];
		swap(x,y),x[sa[1]]=1,num=1;
		for(rint i=2;i<=n;++i)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(num==n)break;m=num;
	}
}
void get_Height() {
	for(rint i=1;i<=n;++i)rk[sa[i]]=i;
	for(rint i=1,k=0;i<=n;++i) {
		if(rk[i]==1)continue;
		if(k)--k;
		rint j=sa[rk[i]-1];
		while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])++k;
		height[rk[i]]=k;
	}
}
signed main() {
	T=rd();
	while(T--) {
		memset(sa,0,sizeof(sa));
		memset(t,0,sizeof(t));
		memset(height,0,sizeof(height));
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		scanf("%s",s+1);
		n=strlen(s+1);
		get_SA();
		get_Height();
		int ans=n*(n+1)/2;
		for(rint i=1;i<=n;++i)ans-=height[i];
		printf("%d\n",ans);
	}
	return 0;
}