#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#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 DS{
	int id_tot;
	map<int,int> id;
	vector<set<int>> h;
	struct node{
		int l,r,cnt;
		bool operator <(const node &y)const{
			if (l!=y.l)return l<y.l;
			if (r!=y.r)return r<y.r;
			return cnt<y.cnt;
		}
	};
	node make_node(int l,int r,int cnt){
		node ans;
		ans.l=l,ans.r=r,ans.cnt=cnt;
		return ans;
	}
	set<node> c;
	struct node2{
		int v;
		node e;
		bool operator <(const node2 &y)const{
			if (v!=y.v)return v<y.v;
			return e<y.e;
		}
	};
	node2 make_node2(int v,node e){
		node2 ans;
		ans.v=v,ans.e=e;
		return ans;
	}
	set<node2> d;
	ll sum;
	int get_r(int x){
		set<node>::iterator it=c.lower_bound(make_node(x,x,0));
		if (it==c.end()||(*it).l>x)it--;
		return (*it).r;
	}
	void out(){
		set<node>::iterator it=c.begin();
		while(it!=c.end()){
			int r=(*it).r;
			int t=id[r]-1;
			for (set<int>::iterator _it=h[t].begin();_it!=h[t].end();_it++)cout<<(*_it)<<' '<<r<<endl;
			it++;
		}
		return;
	}
	void ins_c(node qwq){
		node pre=make_node(-1,-1,-1),nxt=make_node(-1,-1,-1);
		set<node>::iterator it=c.lower_bound(qwq);
		if (it!=c.end())nxt=(*it);
		if (it!=c.begin()){
			set<node>::iterator _it=it;
			_it--;
			pre=(*_it);
		}
		c.insert(qwq);
		if (nxt.l!=-1&&pre.l!=-1)d.erase(make_node2(nxt.l-pre.r,pre));
		if (pre.l!=-1)d.insert(make_node2(qwq.l-pre.r,pre));
		if (nxt.l!=-1)d.insert(make_node2(nxt.l-qwq.r,qwq));
		sum+=1ll*qwq.r*qwq.cnt;
		return;
	}
	void del_c(node qwq){
		c.erase(qwq);
		node pre=make_node(-1,-1,-1),nxt=make_node(-1,-1,-1);
		set<node>::iterator it=c.lower_bound(qwq);
		if (it!=c.end())nxt=(*it);
		if (it!=c.begin()){
			set<node>::iterator _it=it;
			_it--;
			pre=(*_it);
		}
		if (nxt.l!=-1&&pre.l!=-1)d.insert(make_node2(nxt.l-pre.r,pre));
		if (pre.l!=-1)d.erase(make_node2(qwq.l-pre.r,pre));
		if (nxt.l!=-1)d.erase(make_node2(nxt.l-qwq.r,qwq));
		sum-=1ll*qwq.r*qwq.cnt;
		return;
	}
	void ins(int x,int r){
		if (id[r]==0){
			id[r]=++id_tot;
			set<int> qwq;
			qwq.insert(x);
			h.push_back(qwq);
			ins_c(make_node(x,r,1));
		}
		else{
			int t=id[r]-1;
			del_c(make_node((*h[t].begin()),r,h[t].size()));
			h[t].insert(x);
			ins_c(make_node((*h[t].begin()),r,h[t].size()));
		}
		return;
	}
	void del(int x,int r){
		int t=id[r]-1;
		del_c(make_node((*h[t].begin()),r,h[t].size()));
		h[t].erase(x);
		if (h[t].size()>0)ins_c(make_node((*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.begin()!=d.end()&&(*d.begin()).v<=len_r){
			set<node>::iterator it=c.find((*d.begin()).e);
			set<node>::iterator _it=it;
			ans+=1ll*((*d.begin()).v-last)*sum;
			last=(*d.begin()).v;
			_it++;
			node qwq=make_node((*it).l,(*_it).r,(*it).cnt+(*_it).cnt);
			merge(id[(*it).r]-1,id[(*_it).r]-1);
			del_c(*it);
			del_c(*_it);
			ins_c(qwq);
		}
		ans+=1ll*(len_r-last+1)*sum;
		return ans;
	}
	void 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]=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];
	}
	return;
}
void upd_ds(int now,int t0,int t1){
	if (endpos[now]!=0){
		int x=endpos[now];
		int r=ds[t0].get_r(x);
		ds[t1].ins(x,r);
		ds[t0].del(x,r);
	}
	for (int i=first[now];i;i=nxt[i])upd_ds(v[i],t0,t1);
	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]){
			upd_ds(v[i],now,v[i]);
			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]);
	}
	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(i,i);
		dfs2(0);
		for (int i=1;i<=n;i++)ans-=1ll*i*i;
		cout<<ans<<endl;
		clear();
	}
	return 0;
}