#include <bits/stdc++.h>

using namespace std;

const int M = 2e5 + 239;
const int L = 18;
const int B = 500;

typedef long long ll;

vector<int> suffix_array(string s) {
    int n = (int)s.size() + 1;
    vector<int> a(n), b(n), id(n);
    vector<pair<int, int>> st;
    for (int i = 0; i < n - 1; i++) {
        a[i] = s[i] - 'a' + 1;
    }
    a[n - 1] = 0;
    for (int i = 0; i < n; i++) {
        id[i] = i;
    }
    sort(id.begin(), id.end(), [&](int i, int j) {
        return a[i] < a[j];
    });
    for (int t = 1; t < n; t <<= 1) {
        for (int i = 0; i < n; ++i) {
            b[i] = a[(i + t) % n];
        }
        int l = 0, cnt = 0;
        while (l < n) {
            int r = l;
            while (r < n && a[id[l]] == a[id[r]]) {
                ++r;
            }
            sort(id.begin() + l, id.begin() + r, [&](int i, int j) {
                return b[i] < b[j];
            });
            a[id[l]] = ++cnt;
            for (int m = l + 1; m < r; m++) {
                if (b[id[m - 1]] < b[id[m]]) {
                    cnt++;
                }
                a[id[m]] = cnt;
            }
            l = r;
        }
    }
    return vector<int>(id.begin() + 1, id.end());
}

vector<int> kasai(string s, const vector<int>& a) {
    int n = (int)s.size();
    vector<int> t(n);
    for (int i = 0; i < n; i++) {
        t[a[i]] = i;
    }
    vector<int> lcp(n - 1);
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (t[i] == n - 1) {
            continue;
        }
        while (s[i + k] == s[a[t[i] + 1] + k] && a[t[i] + 1] + k < n && i + k < n) {
            k++;
        }
        lcp[t[i]] = k;
        k = max(0, k - 1);
    }
    return lcp;
}

int lg[M];
int n;
string s;
int dp[L][M];
vector<int> a, pos, lcp;
int hook[M], prev_l[M], max_l[M], last_l[M];
int cand[M], cnt_cand;

void add_list(int id, int item) {
    max_l[id] = max(max_l[id], item);
    prev_l[item] = last_l[id];
    last_l[id] = item;
}

void clear_list(int id) {
    max_l[id] = -1;
    last_l[id] = -1;
}

int get_lcs(int i, int j) {
    if (i == j) {
        return i + 1;
    }
    i = pos[i];
    j = pos[j];
    if (i > j) {
        swap(i, j);
    }
    int l = lg[j - i];
    return min(dp[l][i], dp[l][j - (1 << l)]);
}

void solve() {
    cin >> s;
    n = (int)s.size();

    string s_rev = s;
    reverse(s_rev.begin(), s_rev.end());
    a = suffix_array(s_rev);
    lcp = kasai(s_rev, a);
    pos.resize(n);
    for (int i = 0; i < n; i++) {
        a[i] = n - 1 - a[i];
    }
    for (int i = 0; i < n; i++) {
        pos[a[i]] = i;
    }

    for (int i = 0; i < n - 1; i++) {
        dp[0][i] = lcp[i];
    }
    for (int l = 1; l < L; l++) {
        for (int i = 0; i < n - 1; i++) {
            int r = (i + (1 << (l - 1)));
            if (r >= n - 1) {
                dp[l][i] = dp[l - 1][i];
            } else {
                dp[l][i] = min(dp[l - 1][i], dp[l - 1][r]);
            }
        }
    }

    ll ans = 0;
    for (int r = 1; r < n; r++) {
        ans += (ll)r * (ll)(r + 1) / 2;
    }

    for (int i = 0; i < n; i++) {
        prev_l[i] = -1;
        clear_list(i);
    }

    ll sum = 0;
    hook[0] = 0;
    int ln = (n / B) + 1;

    for (int r = 1; r < n; r++) {
        hook[r] = r;
        sum += r;

        cnt_cand = 0;
        auto update = [&](int pt, int d) {
            int t = a[pt];
            if (t + 1 >= r - B || d <= B + 1 || max_l[t + 1] == -1 || r - max_l[t + 1] + 1 > d) {
                return;
            }
            int p = last_l[t + 1];
            clear_list(t + 1);
            while (p != -1) {
                if (r - p + 1 <= d) {
                    cand[cnt_cand++] = p;
                }
                int new_p = prev_l[p];
                if (r - p + 1 > d) {
                    add_list(t + 1, p);
                }
                p = new_p;
            }
        };

        int d = n;
        for (int pt = pos[r] - 1; pt >= 0 && pt > pos[r] - ln; pt--) {
            d = min(d, lcp[pt]);
            if (d <= B + 1) {
                break;
            }
            update(pt, d);
        }
        d = n;
        for (int pt = pos[r] + 1; pt < n && pt < pos[r] + ln; pt++) {
            d = min(d, lcp[pt - 1]);
            if (d <= B + 1) {
                break;
            }
            update(pt, d);
        }

        if (cnt_cand > 0) {
            sort(cand, cand + cnt_cand); // possible log
        }

        auto upd_position = [&](int i) {
            if (hook[i] > 0 && get_lcs(hook[i] - 1, r) >= r - i + 1) {
                sum -= hook[i];
                hook[i] = hook[hook[i] - (r - i + 1)];
                sum += hook[i];
            }
            if (i <= r - B) {
                add_list(hook[i], i);
            }
        };

        for (int pt = 0; pt < cnt_cand; pt++) {
            upd_position(cand[pt]);
        }
        for (int i = max(0, r - B); i <= r; i++) {
            upd_position(i);
        }

        ans -= sum;
    }

    cout << ans << "\n";
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif

    for (int i = 1; i < M; i++) {
        int t = lg[i - 1];
        while ((1 << (t + 1)) <= i) {
            t++;
        }
        lg[i] = t;
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}