#include <bits/stdc++.h>
using namespace std;
char S[400005];
int n;
namespace sam {
int ch[400005][26], lk[400005], len[400005], nd = 1, las = 1;
void init() {
    for (int i = 0; i <= nd; i++) {
        memset(ch[i], 0, 104);
        lk[i] = len[i] = 0;
    }
    nd = las = 1;
}
void extend(int c) {
    int x = ++nd, p = las;
    las = x;
    len[x] = len[p] + 1;
    for (; p && !ch[p][c]; p = lk[p]) ch[p][c] = x;
    if (!p) return lk[x] = 1, void();
    int q = ch[p][c];
    if (len[q] == len[p] + 1)
        return lk[x] = q, void();
    int cl = ++nd;
    len[cl] = len[p] + 1;
    memcpy(ch[cl], ch[q], 104);
    lk[cl] = lk[q], lk[q] = lk[x] = cl;
    for (; p && ch[p][c] == q; p = lk[p]) ch[p][c] = cl;
}
}  // namespace sam
struct Runs {
    int l, r, p;
    bool operator==(const Runs &j) {
        return l == j.l && r == j.r && p == j.p;
    }
};
const long long mod1 = 995053212556338707;
const long long bas1 = 315, bas2 = 79;
const int maxn = 4e5 + 5;
char t[maxn];
int m;
namespace getRuns {
struct Hash {
    long long p[maxn], h[maxn];
    long long mod, buf;
    Hash(long long _buf, long long _mod) {
        buf = _buf;
        mod = _mod;
    }
    void Init(char *s, int n) {
        p[0] = 1;
        h[0] = 0;

        for (int i = 1; i <= n; i++) {
            p[i] = (__int128)p[i - 1] * buf % mod;
            h[i] = ((__int128)h[i - 1] * buf + s[i] - 'a' + 1) % mod;
        }
    }
    bool tl(int u, int v, int len) {
        return (h[u] - h[v] + (__int128)(h[v - len] - h[u - len]) * p[len]) % mod == 0;
    }
    bool tr(int u, int v, int len) {
        return (h[u + len - 1] - h[v + len - 1] + (__int128)(h[v - 1] - h[u - 1]) * p[len]) % mod == 0;
    }
    int get(int l, int r) {
        return (h[r] + (__int128)(mod - h[l - 1]) * p[r - l + 1] % mod) % mod;
    }
} h1(bas1, mod1);  // h2(bas2,mod2);

int extr(int x, int y) {
    int l = 0, r = m - max(x, y) + 1, res = 0;

    while (l <= r) {
        int mid = l + r >> 1;
        if (h1.tr(x, y, mid)) {
            // if (h1.tr(x, y, mid) && h2.tr(x, y, mid)) {
            res = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }

    return res;
}
int extl(int x, int y) {
    int l = 0, r = min(x, y), res = 0;

    while (l <= r) {
        int mid = l + r >> 1;
        if (h1.tl(x, y, mid)) {
            // if (h1.tl(x, y, mid) && h2.tl(x, y, mid)) {
            res = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }

    return res;
}
vector<Runs> raw_runs(0);
int CMP(int x, int y) {
    if (x == y)
        return 0;

    int l = extr(x, y);
    return t[x + l] < t[y + l] ? -1 : 1;
}
void Check(int i, int j) {
    int p = j - i + 1;
    int x = i - extl(i - 1, j), y = j + extr(i, j + 1);

    if (y - x + 1 >= p * 2)
        raw_runs.push_back({x, y, p});
}
int st[maxn], top;
void init() {
    for (int i = m; i; i--) {
        while (top && CMP(i, st[top]) <= 0)
            top--;

        if (top)
            Check(i, st[top] - 1);

        st[++top] = i;
    }

    top = 0;

    for (int i = m; i; i--) {
        while (top && CMP(i, st[top]) >= 0)
            top--;

        if (top)
            Check(i, st[top] - 1);

        st[++top] = i;
    }
}
}  // namespace getRuns
void solve() {
    cin >> S;
    n = strlen(S);
    long long ans = 0;
    sam ::init();
    for (int i = 0; i < n; i++) {
        sam ::extend(S[i] - 'a');
        t[i + 1] = S[i];
        int x = sam ::las;
        ans += sam ::len[x] - sam ::len[sam ::lk[x]];
    }
    m = n;
    getRuns::h1.Init(t, m);
    // getRuns::h2.Init(t, m);
    getRuns::init();
    sort(getRuns::raw_runs.begin(), getRuns::raw_runs.end(), [](const Runs &A, const Runs &B) {
        return A.l == B.l ? (A.r == B.r ? A.p < B.p : A.r < B.r) : A.l < B.l;
    });
    int tot = std::unique(getRuns::raw_runs.begin(), getRuns::raw_runs.end()) - getRuns::raw_runs.begin();
    getRuns::raw_runs.resize(tot);
    unordered_map<long long, int> mp(n * 15);
    for (auto [l, r, p] : getRuns::raw_runs) {
        for (int i = 0; i < p; i++) {
            int t = (r - l + 1 - i) / p - 1;
            if (t) {
                long long h = getRuns::h1.get(l + i, l + i + p - 1);
                int &v = mp[h];
                if (t > v) v = t;
            } else
                break;
        }
    }
    getRuns::raw_runs.clear();
    getRuns::top = 0;
    for (auto [x, y] : mp) ans -= y;
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}