#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <climits>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <iomanip>

#define ALL(v) v.begin(), v.end()
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REPD(i, a, b) for(int i = a; i > b; i--)
#define REPLL(i, a, b) for(ll i = a; i < b; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FORLL(i, a, b) for(ll i = a; i <= b; i++)
#define INF 1000000001

#define vit vector<int>::iterator
#define sit set<int>::iterator
#define vi vector<int>
#define vpii vector<pii >

#define ll long long
#define ld long double

#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pld pair<ld, ld>
#define st first
#define nd second

#define EPS 1e-9
#define PI acos(-1.0)
#define MAXN 10007

using namespace std;

int z, n, m, a, b;

/// suffix array in O(nlogn) and O(n) memory
/// always false sign # at the end!

int temp_suf[MAXN];
int lcp[MAXN];
int suf[MAXN], ra[MAXN], c[MAXN];
char t[MAXN];

void count_sort(int k, int n, int* suf) {
	int i, sum, maxi = max(300, n);
	memset(c, 0, sizeof c);
	REP(i, 0, n) c[i + k < n ? ra[i + k] : 0]++;
	for (i = sum = 0; i < maxi; i++) {
		int t = c[i];
		c[i] = sum;
		sum += t;
	}
	REP(i, 0, n) temp_suf[c[suf[i] + k < n ? ra[suf[i] + k] : 0]++] = suf[i];
	REP(i, 0, n) suf[i] = temp_suf[i];
}

void suf_array(const char *t, int n, int* suf) {
	int k, r;
	REP(i, 0, n) {
		ra[i] = t[i];
		suf[i] = i;
	}
	for (k = 1; k < n; k <<= 1) {
		count_sort(k, n, suf);
		count_sort(0, n, suf);
		temp_suf[suf[0]] = r = 0;
		REP(i, 1, n) temp_suf[suf[i]] = (ra[suf[i]] == ra[suf[i - 1]] && ra[suf[i] + k] == ra[suf[i - 1] + k] ? r : ++r);
		REP(i, 0, n) ra[i] = temp_suf[i];
	}
}

/// LCP in O(n)

int r[MAXN];
void count_lcp(const char *t,  int n, int *suf, int *lcp) {
    int l = 0;
    REP(i, 0, n) r[suf[i]] = i;
    REP(i, 0, n) {
        if(r[i] == n-1) continue;
        int m = suf[r[i]+1];
        while(l+i < n && l+m < n && t[l + i] == t[l + m]) l++;
        lcp[r[i]] = l;
        l = max(0, l-1);
    }
}

int main()
{
	scanf("%d", &z);

    while(z--) {
        scanf("%s", t);
        n = strlen(t);
        t[n++] = '@'; t[n] = 0;
        suf_array(t, n, suf);
        count_lcp(t, n, suf, lcp);
        int ret = n*(n-1)/2;
        REP(i, 0, n-1) ret -= lcp[i];
        printf("%d\n", ret);
    }

    return 0;
}