RT

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>

using namespace std;

template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}

typedef long long ll;

const int INF = 2139062143;

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl

template <typename T> void read (T &x) {
	x = 0; bool f = 1; char ch;
	do {ch = getchar(); if (ch == '-') f = 0;} while (ch > '9' || ch < '0');
	do {x = x * 10 + ch - '0'; ch = getchar();} while (ch >= '0' && ch <= '9');
	x = f ? x : -x;
}

template <typename T> void write (T x) {
	if (x < 0) x = ~x + 1, putchar ('-');
	if (x > 9) write (x / 10);
	putchar (x % 10 + '0');
}

const int N = 500000 + 7; 
const int M = 300 + 5;

int T;

struct SA {
	
	int n, m, x[N], y[N], sa[N], rk[N], buk[M], height[N];
	char s[N];	
	
	inline void GET_SA() {
	    for(int i = 1; i <= n; i++) x[i] = s[i], ++ buk[s[i]];
	    for(int i = 1; i <= m; i++) buk[i] += buk[i - 1];
	    for(int i = n; i >= 1; i--) sa[buk[x[i]] -- ] = i;
	    for(int k = 1; k <= n; k <<= 1) {
	        int num = 0;
	        for(int  i = n - k + 1; i <= n; i++) y[++num] = i;
	        for(int i = 1; i <= n; i++) if(sa[i] > k) y[++num] = sa[i] - k;
	        for(int i = 0; i <= m; i++) buk[i] = 0;
	        for(int i = 1; i <= n; i++) ++ buk[x[i]];
	        for(int i = 1; i <= m; i++) buk[i] += buk[i - 1];
	        for(int i = n; i >= 1; i--) sa[buk[x[y[i]]]--] = y[i], y[i] = 0;
	        for(int i = 1; i <= n; i++) swap(x[i], y[i]);
	        x[sa[1]] = 1; num = 1;
	        for(int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
	        if(num == n) break;
	        m = num;
	    }
//	    for(int i = 1; i <= n; i++) printf("%d ", sa[i]); puts("");
	}

	inline void GET_HEIGHT() {
		int k = 0;
		for(int i = 1; i <= n; i++) rk[sa[i]] = i;
		for(int i = 1; i <= n; i++) {
			if(rk[i] == 1) continue;
			if(k) k -- ;
			int j = sa[rk[i] - 1];
			while(j + k <= n && i + k <= n && s[i + k] == s[j + k]) ++ k;
			height[rk[i]] = k; 
		} 
//		for(int i = 1; i <= n; i++) printf("%d ", height[i]); puts("");
	} 
	
	inline void main() {
		scanf("%s", s + 1);
		n = strlen(s + 1); m = 300;	
		for(int i = 0; i <= m; i++) buk[i] = 0;
		for(int i = 1; i <= n; i++) height[i] = rk[i] = sa[i] = x[i] = y[i] = 0;
		GET_SA();
		GET_HEIGHT(); 
		int ans = 0;
		for(int i = 1; i <= n; i++) ans += height[i];
		printf("%d\n", (n * (n + 1) / 2) - ans);
	} 
} sa;

int main() {
	read(T);
	while(T--) sa.main();
	return 0;
}