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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int MAX = 200'447;

struct node
{
   int g[26];
   int link, len;
   int pos;
   void init()
   {
	   FILL(g, -1);
	   len = 0;
	   pos = -1;
	   link = -1;
   }
};

struct automaton
{
    node A[MAX * 2];
    int sz, head;
    void init()
    {
        sz = 1; head = 0;
        A[0].init();
    }
    void add(char c)
    {
        int ch = c - 'a';
        int nhead = sz++;
        A[nhead].init();
        A[nhead].len = A[head].len + 1;
        A[nhead].pos = A[head].len;
        int cur = head;
        head = nhead;
        while(cur != -1 && A[cur].g[ch] == -1)
        {
            A[cur].g[ch] = head;
            cur = A[cur].link;
        }
        if (cur == -1)
        {
            A[head].link = 0;
            return ;
        }
        int p = A[cur].g[ch];
        if (A[p].len == A[cur].len + 1)
        {
            A[head].link = p;
            return ;
        }
        int q = sz++;
        A[q] = A[p];
        A[q].pos = -1;
        A[q].len = A[cur].len + 1;
        A[p].link = A[head].link = q;
        while(cur != -1 && A[cur].g[ch] == p)
        {
            A[cur].g[ch] = q;
            cur = A[cur].link;
        }
    }
    
    int getLinkLen(int x)
    {
		if (A[x].link == -1) return 0;
		return A[A[x].link].len;
	}
} a;

const int INF = 1'000'000'447;
VI g[2 * MAX];
set<int> pos[2 * MAX];
int mn[2 * MAX];
LL ans = 0;

void add(int v, int x)
{
	auto it = pos[v].lower_bound(x);
	if (it != pos[v].end())
		mn[v] = min(mn[v], *it - x);
	if (it != pos[v].begin())
	{
		it--;
		mn[v] = min(mn[v], x - *it);
	}
	pos[v].insert(x);
}

void dfs(int v)
{
	if (a.A[v].pos != -1)
		pos[v].insert(a.A[v].pos);
	for (auto& to : g[v])
	{
		dfs(to);
		if (SZ(pos[to]) > SZ(pos[v]))
			swap(pos[to], pos[v]);
	}
	for (auto& to : g[v])
	{
		for (auto x : pos[to])
			add(v, x);
	}
	int l = a.getLinkLen(v);
	int r = a.A[v].len;
	ans -= max(0, r - max(l, mn[v] - 1));
}

void solve()
{
	a.init();
	
	string s;
	cin >> s;
	for (auto c : s)
		a.add(c);
	FOR (i, 0, a.sz)
	{
		ans += a.A[i].len - a.getLinkLen(i);
		mn[i] = INF;
		if (a.A[i].link != -1)
			g[a.A[i].link].PB(i);
	}
	
	dfs(0);
	
	cout << ans << '\n';
	
	FOR (i, 0, a.sz)
	{
		g[i].clear();
		pos[i].clear();
	}
	ans = 0;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed;
	
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}