#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ;
using ll = long long ;
cs int N = 4e5 + 5, M = 105; 

void cmx(ll & x , ll y) {
    if(x < y) x = y; 
}

int T, n; 
char S[N];
namespace sam {
int ch[N][26], lk[N], len[N], 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; 
}
}

struct run {
    int l, r, p;
} ;
vector <run> runs; 

cs ll mod = 995053212556338707, B = 223; 

ll ha[N], pw[N];

ll add(ll a, ll b) {
    return a + b >= mod ? a + b - mod : a + b; 
}
ll dec(ll a, ll b) {
    return a - b < 0 ? a - b + mod : a - b; 
}
ll mul(ll a, ll b) {
    return (__int128_t) a * b % mod; 
}

ll has(int l, int r) {
    if(l > r) return 0;
    return dec(ha[r], mul(ha[l - 1], pw[r - l + 1]));
}

int lcp(int x, int y) {
    int l = 0, r = min(n - x + 1, n - y + 1);
    while(l < r) {
        int mid = (l + r + 1) >> 1; 
        if(has(x, x + mid - 1) == has(y, y + mid - 1)) l = mid; 
        else r = mid - 1; 
    } return l;
}
int lcs(int x, int y) {
    int l = 0, r = min(x, y);
    while(l < r) {
        int mid = (l + r + 1) >> 1; 
        if(has(x - mid + 1, x) == has(y - mid + 1, y)) l = mid; 
        else r = mid - 1;
    } return l;
}

bool cmp(int x, int y) {
    int l = lcp(x, y);
    if(x + l > n) return true; 
    if(y + l > n) return false; 
    return S[x + l] < S[y + l];
}

map <pi, int> ex; 

void ins(int l, int r) {
    int p = r - l;
    int l1 = lcp(l, r);
    int l2 = lcs(l - 1, r - 1);
    int L = l - l2, R = r + l1 - 1; 
    if(ex[pi(L, R)]) return ; 
    ex[pi(L, R)] = 1; 
    if(R - L + 1 >= 2 * p) 
        runs.pb((run){L, R, p});
}

void Run(int o) {
    static int s[N];
    int top = 0; s[++ top] = n + 1; 
    for(int i = n;i; i--) {
        while(top > 1 && cmp(i, s[top]) == o) -- top;
        ins(i, s[top]); s[++ top] = i; 
    }
}
map <ll, int> mp; 
void Main() {
    scanf("%s", S + 1);
    n = strlen(S + 1);
    ll ans = 0; 
    sam :: init();
    for(int i = 1; i <= n; i++) {
        sam :: extend(S[i] - 'a');
        int x = sam :: las; 
        ans += sam :: len[x] - sam :: len[sam :: lk[x]];
    }
    // cout << ans << '\n';
    pw[0] = 1; 
    for(int i = 1; i <= n; i++)
        pw[i] = mul(pw[i - 1], B);
    for(int i = 1; i <= n; i++)
        ha[i] = add(mul(ha[i - 1], B), (S[i] - 'a')); 
    runs.clear();
    ex.clear();
    Run(0);
    Run(1);
    mp.clear();
    for(auto [l, r, p] : runs) {
        int t = (r - l + 1) / p - 1; 
        for(int i = 0; i < p; i++) {
            ll h = has(l, l + p - 1);
            if(t > mp[h]) mp[h] = t;  
        }
    }
    for(auto [x, y] : mp) ans -= y; 
    cout << ans << '\n';
}

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    cin >> T; 
    while(T--) {
        Main();
    }
    return 0; 
}