// MagicDark
#include <bits/stdc++.h>
#define link fdskjfhsdkjhfkjdshfkjdxhbgjkfdbgjkshdbgjh
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T &x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T &x, T y) {return x = min(x, y);}
const int N = 4e5 + 10;
int n, tot, son[N][26], link[N], len[N], endpos[N], last;
ll ans;
string st;
vector <int> v[N];
void init() {
	while (tot) v[tot].clear(), endpos[tot] = 0, ms(son[tot--], 0);
	last = tot = 1;
}
int extend(int c) {
	int nw = ++tot, p = last;
	len[nw] = len[p] + 1;
	while (p && !son[p][c]) {
		son[p][c] = nw;
		p = link[p];
	}
	if (!p) link[nw] = 1;
	else {
		int q = son[p][c];
		if (len[p] + 1 == len[q]) link[nw] = q;
		else {
			int cl = ++tot;
			F(i, 0, 25) son[cl][i] = son[q][i];
			len[cl] = len[p] + 1;
			link[cl] = link[q];
			while (p && son[p][c] == q) {
				son[p][c] = cl;
				p = link[p];
			}
			link[nw] = link[q] = cl;
		}
	}
	return last = nw;
}
int sz[N], mxson[N];
void dfs(int x) {
	// debug << x << " " << endpos[x] << " " << len[x] << endl;
	sz[x] = !!endpos[x];
	mxson[x] = 0;
	for (int i: v[x]) {
		// debug << x << " -> " << i << endl;
		dfs(i);
		sz[x] += sz[i];
		if (sz[i] >= sz[mxson[x]]) mxson[x] = i;
	}
}
template <typename _Tp> class Q {
    priority_queue<_Tp, vector <_Tp>, greater <_Tp>> _Val, _Del; bool _Op; size_t _Siz;
    void flush() {
        while(!_Del.empty() && !_Val.empty() && _Del.top() == _Val.top()) _Val.pop(), _Del.pop(); _Op = 0;
    }
    public:
    Q() : _Op(0), _Siz(0) {}
    size_t size() {return _Siz;}
    void push(const _Tp &x) {_Siz++; _Val.push(x);}
    _Tp top() {
        assert(_Siz); if(_Op) flush(); assert(!_Val.empty()); return _Val.top();
    }
    void pop() {
        assert(_Siz); _Siz--;
        if(_Op) flush(); _Op = (!_Del.empty());
        assert(!_Val.empty()); _Val.pop();
    }
    bool empty() {return _Siz == 0;}
    void erase(const _Tp &x) {
        assert(_Siz); _Siz--;
        if(_Op) flush(); assert(!_Val.empty());
        if(x == _Val.top()) {
            _Val.pop(); _Op = 1; return;
        }
        assert(x > _Val.top()); _Del.push(x);
    }
    void clear() {
        _Op = _Siz = 0; priority_queue<_Tp> _Tx, _Ty;
        swap(_Val, _Tx), swap(_Del, _Ty);
    }
};
vector <pair <int, int>> w;
struct DS {
	int tot;
	// map <int, int> id;
	vector <Q <int>> h;
	set <pair <int, int>> s;
	priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
	ll cur;
	void build() {
		tot = cur = 0;
		h.clear(), s.clear();
		while (q.size()) q.pop();
		sort(all(w));
		for (int i = 0, j; i <= SZ(w); i = j + 1) {
			j = i;
			int mx = w[i].second;
			while (j < SZ(w) && w[j + 1].first <= mx) chkmax(mx, w[++j].second);
			{
				Q <int> t;
				h.push_back(t);
			}
			F(k, i, j) h.back().push(w[k].first);
			cur += (ll) (j - i + 1) * mx;
			if (s.size()) q.emplace(w[j].first - s.rbegin() -> first, mx);
			s.emplace(mx, tot);
			tot++;
		}
		// debug << tot << " " << h.size() << " " << s.size() << " " << q.size() << endl;
	}
	void del(int x) {
		// debug << x << endl;
		// for (auto [a, b]: s) debug << a << " " << b << endl;
		auto it = s.lower_bound(make_pair(x, 0));
		assert(it != s.end());
		// auto g = h[it -> second];
		// debug << it -> second << " " << h[it -> second].size() << endl;
		// while (g.size()) {
		// 	cout << g.top() << " ";
		// 	g.pop();
		// }
		// debug << endl;
		// debug << "! " << x << endl;
		cur -= it -> first;
		h[it -> second].erase(x);
		if (h[it -> second].empty()) {
			it = s.erase(it);
			if (it != s.end() && it != s.begin()) q.emplace(h[it -> second].top() - (prev(it) -> first), it -> first);
		} else if (it != s.begin()) q.emplace(h[it -> second].top() - (prev(it) -> first), it -> first);
	}
	void merge(int x, int y) {
		if (h[x].size() > h[y].size()) swap(h[x], h[y]);
		while (h[x].size()) {
			h[y].push(h[x].top());
			h[x].pop();
		}
	}
	int query(int x) {
		auto it = s.lower_bound(make_pair(x, 0));
		assert(it != s.end());
		return it -> first;
	}
	void dot(int l, int r) {
		// debug << " ) " << cur << endl;
		int lst = l;
		while (q.size() && q.top().first <= r) {
			auto [x, y] = q.top(); q.pop();
			auto it = s.lower_bound(make_pair(y, 0));
			if (it == s.end()) continue;
			// assert(it != s.end());
			if (it == s.begin()) continue;
			auto [a, b] = * it;
			it--;
			auto [c, d] = * it;
			if (h[b].top() - c != x) continue;
			ans += (ll) cur * (x - lst);
			lst = x;
			cur += (ll) h[d].size() * (a - c);
			merge(d, b);
			s.erase(it);
			// debug << d << " " << b << " " << h[d].size() << " " << h[b].size() << endl;
		}
		ans += (ll) (r - lst + 1) * cur;
	}
} ds[N];
void dfs3(int a, int x) {
	if (endpos[x]) {
		// debug << "~ " << a << " " << x << " " << ds[a].query(endpos[x]) << endl;
		w.emplace_back(endpos[x], ds[a].query(endpos[x]));
		ds[a].del(endpos[x]);
	}
	for (int i: v[x]) dfs3(a, i);
}
void dfs2(int x) {
	ds[x].dot(len[link[x]] + 1, len[x]);
	if (endpos[x]) {
		// debug << x << " " << endpos[x] << " " << ds[x].s.size() << endl;
		ds[x].del(endpos[x]);
	}
	// debug << x << " : " << ds[x].cur << " " << len[link[x]] + 1 << " " << len[x] << ' ' << ans << endl;
	for (int i: v[x])
		if (i != mxson[x]) {
			w.clear();
			dfs3(x, i);
			// debug << x << endl;
			// for (auto [a, b]: w) debug << a << " " << b << endl;
			ds[i].build();
			dfs2(i);
		}
	if (mxson[x]) {
		swap(ds[x], ds[mxson[x]]);
		dfs2(mxson[x]);
	}
}
void zhk() {
	ans = 0;
	init();
	cin >> st;
	reverse(all(st));
	// debug << tot << endl;
	n = st.size(); st = ' ' + st;
	F(i, 1, n) endpos[extend(st[i] - 'a')] = i, ans -= (ll) (n - i + 1) * (i + n) / 2;
	// debug << tot << endl;
	F(i, 2, tot) v[link[i]].push_back(i);//, debug << link[i] << " " << i << endl;
	dfs(1);
	w.clear();
	F(i, 1, n) w.emplace_back(i, i);
	ds[1].build();
	dfs2(1);
	cout << ans << '\n';
}
signed main() {
	cin.tie(0) -> sync_with_stdio(0); // don't use puts
	int _ = 1;
	cin >> _;
	while (_--) zhk();
	return 0;
}
/* why?
*/