rt，提交记录。

不太清楚原理是什么，代码：

#include<iostream>
#include<cstring>
using namespace std;

const int N=1e7+5;

char s[N];
int len,M=123;

namespace suffixArray{;
	
	int SA[N],x[N]/*第一关键字*/,y[N]/*第二关键字*/;
	int bucket[N];
	int height[N];
	
	inline void solve(){;
		for(int i=1;i<=len;++i)x[i]=s[i],++bucket[s[i]];
		for(int i=1;i<M;++i)bucket[i]+=bucket[i-1];
		for(int i=len;i>=1;--i)SA[bucket[x[i]]--]=i;
		for(int w=1;w<=len;w<<=1){;
			int idx=0;
			for(int i=len-w+1;i<=len;++i)y[++idx]=i;
			for(int i=1;i<=len;++i)if(SA[i]>w)y[++idx]=SA[i]-w;
			memset(bucket,0,sizeof bucket);
			for(int i=1;i<=len;++i)++bucket[x[i]];
			for(int i=2;i<N;++i)bucket[i]+=bucket[i-1];
			for(int i=len;i>=1;--i)SA[bucket[x[y[i]]]--]=y[i],y[i]=0;
			swap(x,y);//交换后 x 即为 rk
			x[SA[1]]=1,idx=1;
			for(int i=2;i<=len;++i)x[SA[i]]=(y[SA[i]]==y[SA[i-1]]&&y[SA[i]+w]==y[SA[i-1]+w])?idx:++idx;
			if(idx==len)break ;
			M=idx;
		};
		int k=0;
		for(int i=1;i<=len;++i)x[SA[i]]=i;
		for(int i=1;i<=len;++i){
			if(x[i]==1) continue; 
			if(k)--k;
			int j=SA[x[i]-1];
			while(j+k<=len&&i+k<=len&&s[i+k]==s[j+k])++k;
			height[x[i]]=k;
	    }
		return ;
	};
		
}using namespace suffixArray;

inline void work(){
	// memset(SA,0,sizeof SA);
	// memset(x,0,sizeof x);
	// memset(y,0,sizeof y);
	// memset(bucket,0,sizeof bucket);
	// memset(height,0,sizeof height);
    len=0,M=123;
	char c=getchar();
	while(!isalpha(c))c=getchar();
	while(isalpha(c))s[++len]=c,c=getchar();
	solve();
	int sum=0;
	for(int i=2;i<=len;++i)sum+=height[i];
	cout<<(len+1)*len/2-sum<<"\n";
	return ;
}

signed main(){;
	int T;
	cin>>T;
	while(T--)work();
	return 0;
};