#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ;
using ll = long long ;
using i128 = __int128;
using u128 = __uint128_t;
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 (ha[r] + u128(mod - ha[l - 1]) * pw[r - l + 1]) % mod;
}
i128 has_raw(int l, int r) {
    if(l > r) return 0;
    return ha[r] - (i128) ha[l - 1] * pw[r - l + 1];
}


bool iskmod(i128 x) {
	constexpr i128 mul = []() {
		i128 res = 0;
		for(char c : "93809386772914624520890844190221243419") if(c) {
			res = res * 10 + (c - 48);
		}
		return res;
	}();
	static const ll lim = 2e18;
	x *= mul;
	return -lim < x && x < lim;
}
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; 
		i128 T = has_raw(x, x + mid - 1) - has_raw(y, y + mid - 1);
        if(iskmod(T)) l = mid; 
        else r = mid - 1; 
    } return l;
}
int lcs(int x, int y) {
    int l = 0, r = min(x, y) + 1; 
    while(l < r) {
        int mid = (l + r + 1) >> 1; 
		const i128 T = has_raw(x - mid + 1, x) - has_raw(y - mid + 1, y);
        if(iskmod(T)) 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];
}

set <pi> ex; 

void ins(int l, int r) {
    // cout << "ins " << l << ' ' << r << endl;
    int p = r - l;
    int l1 = lcp(l, r);
    int l2 = lcs(l - 1, r - 1);
    int L = l - l2, R = r + l1 - 1; 
    // cout << L <<' ' << R << ' ' << p << endl;
    if(R - L + 1 >= 2 * p) {
        auto iter = ex.lower_bound(pi(L, R));
        if(iter != ex.end() && *iter == pi(L, R)) return ;
        
        ex.emplace_hint(iter, pi(L, R));
        runs.pb((run){L, R, p}); // , cout << "RUNS " << L << ' ' << R << " " << p << endl;
    }
}

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; 
    }
}

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' + 1); 
    runs.clear();
    ex.clear();
    Run(0);
    Run(1);
    unordered_map <ll, int> mp(n * 15); 
    for(auto [l, r, p] : runs) {
        // cout << l <<' ' << r << ' ' <<p << endl;
        for(int i = 0; i < p; i++) {
            int t = (r - l + 1 - i) / p - 1; 
            if(t) {
                ll h = has(l + i, l + i + p - 1);
                // cout << "FF " << h << ' ' << l + i << ' ' << l + i + p - 1 << ' ' << t << endl;
                int & v = mp[h];
                if(t > v) v = t;
            } else  break;

        }
    }
    for(auto [x, y] : mp)  ans -= y; 
    cout << ans << '\n';
}

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