#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8Y2xpbWl0cz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxpb21hbmlwPgoKI2RlZmluZSBBTEwodikgdi5iZWdpbigpLCB2LmVuZCgpCiNkZWZpbmUgUkVQKGksIGEsIGIpIGZvcihpbnQgaSA9IGE7IGkgPCBiOyBpKyspCiNkZWZpbmUgUkVQRChpLCBhLCBiKSBmb3IoaW50IGkgPSBhOyBpID4gYjsgaS0tKQojZGVmaW5lIFJFUExMKGksIGEsIGIpIGZvcihsbCBpID0gYTsgaSA8IGI7IGkrKykKI2RlZmluZSBGT1IoaSwgYSwgYikgZm9yKGludCBpID0gYTsgaSA8PSBiOyBpKyspCiNkZWZpbmUgRk9SRChpLCBhLCBiKSBmb3IoaW50IGkgPSBhOyBpID49IGI7IGktLSkKI2RlZmluZSBGT1JMTChpLCBhLCBiKSBmb3IobGwgaSA9IGE7IGkgPD0gYjsgaSsrKQojZGVmaW5lIElORiAxMDAwMDAwMDAxCgojZGVmaW5lIHZpdCB2ZWN0b3I8aW50Pjo6aXRlcmF0b3IKI2RlZmluZSBzaXQgc2V0PGludD46Oml0ZXJhdG9yCiNkZWZpbmUgdmkgdmVjdG9yPGludD4KI2RlZmluZSB2cGlpIHZlY3RvcjxwaWkgPgoKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBsZCBsb25nIGRvdWJsZQoKI2RlZmluZSBQQiBwdXNoX2JhY2sKI2RlZmluZSBNUCBtYWtlX3BhaXIKI2RlZmluZSBwaWkgcGFpcjxpbnQsIGludD4KI2RlZmluZSBwbGQgcGFpcjxsZCwgbGQ+CiNkZWZpbmUgc3QgZmlyc3QKI2RlZmluZSBuZCBzZWNvbmQKCiNkZWZpbmUgRVBTIDFlLTkKI2RlZmluZSBQSSBhY29zKC0xLjApCiNkZWZpbmUgTUFYTiAxMDAwNwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCB6LCBuLCBtLCBhLCBiOwoKLy8vIHN1ZmZpeCBhcnJheSBpbiBPKG5sb2duKSBhbmQgTyhuKSBtZW1vcnkKLy8vIGFsd2F5cyBmYWxzZSBzaWduICMgYXQgdGhlIGVuZCEKCmludCB0ZW1wX3N1ZltNQVhOXTsKaW50IGxjcFtNQVhOXTsKaW50IHN1ZltNQVhOXSwgcmFbTUFYTl0sIGNbTUFYTl07CmNoYXIgdFtNQVhOXTsKCnZvaWQgY291bnRfc29ydChpbnQgaywgaW50IG4sIGludCogc3VmKSB7CglpbnQgaSwgc3VtLCBtYXhpID0gbWF4KDMwMCwgbik7CgltZW1zZXQoYywgMCwgc2l6ZW9mIGMpOwoJUkVQKGksIDAsIG4pIGNbaSArIGsgPCBuID8gcmFbaSArIGtdIDogMF0rKzsKCWZvciAoaSA9IHN1bSA9IDA7IGkgPCBtYXhpOyBpKyspIHsKCQlpbnQgdCA9IGNbaV07CgkJY1tpXSA9IHN1bTsKCQlzdW0gKz0gdDsKCX0KCVJFUChpLCAwLCBuKSB0ZW1wX3N1ZltjW3N1ZltpXSArIGsgPCBuID8gcmFbc3VmW2ldICsga10gOiAwXSsrXSA9IHN1ZltpXTsKCVJFUChpLCAwLCBuKSBzdWZbaV0gPSB0ZW1wX3N1ZltpXTsKfQoKdm9pZCBzdWZfYXJyYXkoY29uc3QgY2hhciAqdCwgaW50IG4sIGludCogc3VmKSB7CglpbnQgaywgcjsKCVJFUChpLCAwLCBuKSB7CgkJcmFbaV0gPSB0W2ldOwoJCXN1ZltpXSA9IGk7Cgl9Cglmb3IgKGsgPSAxOyBrIDwgbjsgayA8PD0gMSkgewoJCWNvdW50X3NvcnQoaywgbiwgc3VmKTsKCQljb3VudF9zb3J0KDAsIG4sIHN1Zik7CgkJdGVtcF9zdWZbc3VmWzBdXSA9IHIgPSAwOwoJCVJFUChpLCAxLCBuKSB0ZW1wX3N1ZltzdWZbaV1dID0gKHJhW3N1ZltpXV0gPT0gcmFbc3VmW2kgLSAxXV0gJiYgcmFbc3VmW2ldICsga10gPT0gcmFbc3VmW2kgLSAxXSArIGtdID8gciA6ICsrcik7CgkJUkVQKGksIDAsIG4pIHJhW2ldID0gdGVtcF9zdWZbaV07Cgl9Cn0KCi8vLyBMQ1AgaW4gTyhuKQoKaW50IHJbTUFYTl07CnZvaWQgY291bnRfbGNwKGNvbnN0IGNoYXIgKnQsICBpbnQgbiwgaW50ICpzdWYsIGludCAqbGNwKSB7CiAgICBpbnQgbCA9IDA7CiAgICBSRVAoaSwgMCwgbikgcltzdWZbaV1dID0gaTsKICAgIFJFUChpLCAwLCBuKSB7CiAgICAgICAgaWYocltpXSA9PSBuLTEpIGNvbnRpbnVlOwogICAgICAgIGludCBtID0gc3VmW3JbaV0rMV07CiAgICAgICAgd2hpbGUobCtpIDwgbiAmJiBsK20gPCBuICYmIHRbbCArIGldID09IHRbbCArIG1dKSBsKys7CiAgICAgICAgbGNwW3JbaV1dID0gbDsKICAgICAgICBsID0gbWF4KDAsIGwtMSk7CiAgICB9Cn0KCmludCBtYWluKCkKewoJc2NhbmYoIiVkIiwgJnopOwoKICAgIHdoaWxlKHotLSkgewogICAgICAgIHNjYW5mKCIlcyIsIHQpOwogICAgICAgIG4gPSBzdHJsZW4odCk7CiAgICAgICAgdFtuKytdID0gJ0AnOyB0W25dID0gMDsKICAgICAgICBzdWZfYXJyYXkodCwgbiwgc3VmKTsKICAgICAgICBjb3VudF9sY3AodCwgbiwgc3VmLCBsY3ApOwogICAgICAgIGludCByZXQgPSBuKihuLTEpLzI7CiAgICAgICAgUkVQKGksIDAsIG4tMSkgcmV0IC09IGxjcFtpXTsKICAgICAgICBwcmludGYoIiVkXG4iLCByZXQpOwogICAgfQoKICAgIHJldHVybiAwOwp9Cg==