// MagicDark
#include <bits/stdc++.h>
#include <bits/extc++.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 {
__gnu_pbds ::priority_queue <_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);
}
void jj(Q& x) {
_Siz += x.size();
// x._Siz = 0;
_Val.join(x._Val);
_Del.join(x._Del);
_Op = 1;
}
};
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);
// h[b].jj(h[d]);
// {
// Q <int> x;
// swap(x, h[b]);
// }
s.erase(it);
// {
// auto w = h[d];
// cout << "~ " << w.size() << endl;
// while (w.size()) {
// cout << w.top() << endl;
// w.pop();
// }
// }
// cout << 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?
*/