#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#define ll long long
using namespace std;
int t,n;
ll ans;
char s[200005];
struct sam_node{
	int son[26],len,link;
	sam_node(){
		memset(son,0,sizeof(son));
		len=0,link=-1;
		return;
	}
	void clear(){
		memset(son,0,sizeof(son));
		len=0,link=-1;
		return;
	}
}sam[400005];
int sam_cnt,last;
int sam_ins(char x){
	int p=last;
	int now=++sam_cnt;
	sam[now].len=sam[p].len+1;
	while(p!=-1&&sam[p].son[x-'a']==0){
		sam[p].son[x-'a']=now;
		p=sam[p].link;
	}
	if (p==-1){
		sam[now].link=0;
		last=now;
		return now;
	}
	int q=sam[p].son[x-'a'];
	if (sam[q].len==sam[p].len+1){
		sam[now].link=q;
		last=now;
		return now;
	}
	int clone=++sam_cnt;
	sam[clone]=sam[q];
	sam[clone].len=sam[p].len+1;
	sam[now].link=sam[q].link=clone;
	while(p!=-1&&sam[p].son[x-'a']==q){
		sam[p].son[x-'a']=clone;
		p=sam[p].link;
	}
	last=now;
	return now;
}
int endpos[400005];
int u[400005],v[400005],first[400005],nxt[400005];
int sz[400005],son[400005];
struct seg{
	int l,r,cnt;
	bool operator <(const seg &y)const{
		if (l!=y.l)return l<y.l;
		if (r!=y.r)return r<y.r;
		return cnt<y.cnt;
	}
};
seg make_seg(int l,int r,int cnt){
	seg ans;
	ans.l=l,ans.r=r,ans.cnt=cnt;
	return ans;
}
struct node{
	int v,r;
	bool operator ==(const node &y)const{
		return (v==y.v)&&(r==y.r);
	}
	bool operator <(const node &y)const{
		if (v!=y.v)return v<y.v;
		return r<y.r;
	}
};
node make_node(int v,int r){
	node ans;
	ans.v=v,ans.r=r;
	return ans;
}
struct node_Heap{
	priority_queue<ll> h,_h;
	void ins(node x){
		ll val=(((ll)x.v)<<20)+x.r;
		h.push(-val);
		return;
	}
	void del(node x){
		ll val=(((ll)x.v)<<20)+x.r;
		_h.push(-val);
		return;
	}
	int size(){
		return h.size()-_h.size();
	}
	node top(){
		while((!_h.empty())&&(h.top()==_h.top()))h.pop(),_h.pop();
		node ans=make_node(((-h.top())>>20),((-h.top())&1048575));
		return ans;
	}
	void pop(){
		while((!_h.empty())&&(h.top()==_h.top()))h.pop(),_h.pop();
		h.pop();
		return;
	}
	void clear(){
		while(!h.empty())h.pop();
		while(!_h.empty())_h.pop();
		return;
	}
};
struct DS{
	vector<pair<int,int>> ins;
	int id_tot;
	map<int,int> id;
	vector<set<int>> h;
	set<seg> c;
	node_Heap d;
	ll sum;
	int get_r(int x){
		set<seg>::iterator it=c.lower_bound(make_seg(x,x,0));
		if (it==c.end()||(*it).l>x)it--;
		return (*it).r;
	}
	void build(){
		sort(ins.begin(),ins.end());
		int len=(int)ins.size();
		for (int i=0;i<len;){
			int j=i;
			while(j<len&&ins[j].second==ins[i].second)j++;
			id[ins[i].second]=++id_tot;
			set<int> qwq;
			for (int k=i;k<j;k++)qwq.insert(ins[k].first);
			h.push_back(qwq);
			c.insert(make_seg(ins[i].first,ins[j-1].second,j-i));
			sum+=1ll*ins[j-1].second*(j-i);
			if (i>0)d.ins(make_node(ins[i].first-ins[i-1].second,ins[i-1].second));
			i=j;
		}
		return;
	}
	void ins_c(seg qwq){
		seg pre=make_seg(-1,-1,-1),nxt=make_seg(-1,-1,-1);
		set<seg>::iterator it=c.lower_bound(qwq);
		if (it!=c.end())nxt=(*it);
		if (it!=c.begin()){
			set<seg>::iterator _it=it;
			_it--;
			pre=(*_it);
		}
		c.insert(qwq);
		if (nxt.l!=-1&&pre.l!=-1)d.del(make_node(nxt.l-pre.r,pre.r));
		if (pre.l!=-1)d.ins(make_node(qwq.l-pre.r,pre.r));
		if (nxt.l!=-1)d.ins(make_node(nxt.l-qwq.r,qwq.r));
		sum+=1ll*qwq.r*qwq.cnt;
		return;
	}
	void del_c(seg qwq){
		c.erase(qwq);
		seg pre=make_seg(-1,-1,-1),nxt=make_seg(-1,-1,-1);
		set<seg>::iterator it=c.lower_bound(qwq);
		if (it!=c.end())nxt=(*it);
		if (it!=c.begin()){
			set<seg>::iterator _it=it;
			_it--;
			pre=(*_it);
		}
		if (nxt.l!=-1&&pre.l!=-1)d.ins(make_node(nxt.l-pre.r,pre.r));
		if (pre.l!=-1)d.del(make_node(qwq.l-pre.r,pre.r));
		if (nxt.l!=-1)d.del(make_node(nxt.l-qwq.r,qwq.r));
		sum-=1ll*qwq.r*qwq.cnt;
		return;
	}
	void del(int x,int r){
		int t=id[r]-1;
		del_c(make_seg((*h[t].begin()),r,h[t].size()));
		h[t].erase(x);
		if (h[t].size()>0)ins_c(make_seg((*h[t].begin()),r,h[t].size()));
		return;
	}
	void merge(int x,int y){
		if (h[x].size()>h[y].size())swap(h[x],h[y]);
		for (set<int>::iterator it=h[x].begin();it!=h[x].end();it++)h[y].insert(*it);
		h[x].clear();
		return;
	}
	ll upd(int len_l,int len_r){
		ll ans=0;
		int last=len_l;
		while(d.size()>0&&(d.top()).v<=len_r){
			node d_val=d.top();
			set<seg>::iterator it=c.lower_bound(make_seg(d_val.r+1,d_val.r+1,0));
			it--;
			set<seg>::iterator _it=it;
			ans+=1ll*(d_val.v-last)*sum;
			last=d_val.v;
			_it++;
			seg qwq=make_seg((*it).l,(*_it).r,(*it).cnt+(*_it).cnt);
			merge(id[(*it).r]-1,id[(*_it).r]-1);
			c.erase(*it),sum-=1ll*(*it).r*(*it).cnt;
			c.erase(*_it),sum-=1ll*(*_it).r*(*_it).cnt;
			c.insert(qwq),sum+=1ll*qwq.r*qwq.cnt;
			d.pop();
		}
		ans+=1ll*(len_r-last+1)*sum;
		return ans;
	}
	void clear(){
		ins.clear();
		id_tot=0;
		id.clear();
		h.clear();
		c.clear();
		d.clear();
		sum=0;
		return;
	}
}ds[400005];
void clear(){
	ans=0;
	last=0;
	for (int i=0;i<=sam_cnt;i++){
		sam[i].clear();
		endpos[i]=0;
		u[i]=v[i]=first[i]=nxt[i]=0;
		sz[i]=son[i]=0;
		ds[i].clear();
	}
	sam_cnt=0;
	return;
}
void dfs1(int now){
	sz[now]=0;
	if (endpos[now]!=0)sz[now]=1;
	son[now]=-1;
	for (int i=first[now];i;i=nxt[i]){
		dfs1(v[i]);
		sz[now]+=sz[v[i]];
		if (son[now]==-1||sz[v[i]]>sz[son[now]])son[now]=v[i];
	}
	if (son[now]!=-1&&sz[son[now]]*3/2<=sz[now])son[now]=-1;
	return;
}
void upd_ds(int now,int t0,int t1,int fg){
	if (endpos[now]!=0){
		int x=endpos[now];
		int r=ds[t0].get_r(x);
		ds[t1].ins.push_back(make_pair(x,r));
		if (fg==1)ds[t0].del(x,r);
	}
	for (int i=first[now];i;i=nxt[i])upd_ds(v[i],t0,t1,fg);
	return;
}
void dfs2(int now){
	if (now>0){
		int len_l=sam[sam[now].link].len+1;
		int len_r=sam[now].len;
		ans+=ds[now].upd(len_l,len_r);
	}
	for (int i=first[now];i;i=nxt[i])
		if (v[i]!=son[now]){
			int fg=1;
			if (son[now]==-1)fg=0;
			upd_ds(v[i],now,v[i],fg);
			ds[v[i]].build();
			dfs2(v[i]);
		}
	if (endpos[now]!=0){
		int x=endpos[now];
		int r=ds[now].get_r(x);
		ds[now].del(x,r);
	}
	if (son[now]!=-1){
		swap(ds[now],ds[son[now]]);
		dfs2(son[now]);
	}
	ds[now].clear();
	return;
}
int main(){
	cin>>t;
	while(t--){
		scanf("%s",s+1);
		n=strlen(s+1);
		reverse(s+1,s+1+n);
		for (int i=1;i<=n;i++)endpos[sam_ins(s[i])]=i;
		for (int i=1;i<=sam_cnt;i++){
			u[i]=sam[i].link,v[i]=i;
			nxt[i]=first[u[i]],first[u[i]]=i;
		}
		dfs1(0);
		for (int i=1;i<=n;i++)ds[0].ins.push_back(make_pair(i,i));
		ds[0].build();
		dfs2(0);
		for (int i=1;i<=n;i++)ans-=1ll*i*i;
		cout<<ans<<endl;
		clear();
	}
	return 0;
}