#include<bits/stdc++.h>
using namespace std;

const int maxN = 2e5+7;

struct SAM
{
    int cnt, last, len[maxN*2], lk[maxN*2], tr[maxN*2][26], pos[maxN*2];

    int cpy_node(int idx)
    {
        int id = ++cnt;
        len[id] = len[idx];
        lk[id] = lk[idx];
        memcpy(tr[id], tr[idx], sizeof(tr[id]));
        pos[id] = pos[idx];
        return id;
    }

    void add(int i, int c)
    {
        int u = cpy_node(0), p = last;
        len[u] = len[p]+1; pos[u] = i;
        for(; p && !tr[p][c]; p = lk[p])
        tr[p][c] = u;
        if(!p) lk[u] = 1;
        else
        {
            int q = tr[p][c];
            if(len[q] == len[p]+1) lk[u] = q;
            else
            {
                int cl = cpy_node(q);
                len[cl] = len[p]+1;
                for(; p && tr[p][c] == q; p = lk[p])
                tr[p][c] = cl;
                lk[u] = lk[q] = cl;
            }
        }
        last = u;
    }
    void init(const string& s)
    {
        cnt = 0; last = cpy_node(0);
        for(int i = 0; i < s.size(); ++i)
            add(i+1, s[i]-'a');
    }

    queue<int> bk[maxN];
    int dp[maxN*2], lift[maxN*2][20], f[maxN];

    void solve(const string& s)
    {
        int n = s.size();
        init(s);

        for(int u = 1; u <= cnt; ++u)
            bk[len[u]].push(u);
        for(int i = n; i; --i)
            while(!bk[i].empty())
            {
                int u = bk[i].front();
                bk[i].pop();
                dp[u] = 0;
                for(int c = 0; c < 26; ++c)
                {
                    if(!tr[u][c]) continue;
                    int v = tr[u][c];
                    dp[u] = max(dp[u], dp[v]+1);
                }
            }

        for(int u = 1; u <= cnt; ++u)
        {
            lift[u][0] = 0;
            for(int c = 0; c < 26; ++c)
            {
                if(!tr[u][c]) continue;
                int v = tr[u][c];
                lift[u][0] = v;
                break;
            }
        }
        for(int p = 1; p < 20; ++p)
            for(int u = 1; u <= cnt; ++u)
                lift[u][p] = lift[lift[u][p-1]][p-1];

        queue<tuple<int, int, int, int>> q;
        q.push({1, 1, n, 0});
        while(!q.empty())
        {
            auto [u, l, r, d] = q.front();
            q.pop();

            int nw_u = u, nw_d = d;
            for(int p = 19; p >= 0; --p)
            {
                if(nw_d+(1<<p) > l || !lift[nw_u][p] || dp[lift[nw_u][p]]+nw_d+(1<<p) < r) continue;
                nw_u = lift[nw_u][p];
                nw_d += (1<<p);
            }

            if(nw_d == l)
            {
                f[l] = pos[nw_u]-l+1;
                if(l < r) q.push({nw_u, l+1, r, l});
            }
            else
            {
                for(int c = 0; c < 26; ++c)
                {
                    if(!tr[nw_u][c]) continue;
                    int v = tr[nw_u][c];
                    int m = min(dp[v]+nw_d+1, r);
                    if(l <= m)
                    {
                        q.push({v, l, m, nw_d+1});
                        l = m+1;
                    }
                }
            }
        }

        long long ans = 0;
        for(int i = 1; i <= n; ++i)
            ans += (long long)f[i]*i;
        cout << ans << '\n';
    }
} aut;

void test()
{
    string s; cin >> s;
    aut.solve(s);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    while(t--) test();
    return 0;
}