#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <int> vi;
#define inf (int)1e9

#define maxn 1510

char T[maxn];
int n, c[maxn];
int SA[maxn], RA[maxn], tempRA[maxn], tempSA[maxn];

void countingSort(int k){
    int i, sum, maxi = max(300, n);
    memset(c, 0, sizeof c);
    for(i=0; i<n; i++) c[i + k < n ? RA[i+k] : 0]++;
    for(i = sum = 0; i < maxi; i++){
        int t = c[i]; c[i] = sum; sum += t;
    }
    for(i=0; i<n; i++)
        tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
    for(i=0; i<n; i++) SA[i] = tempSA[i];
}
void constructSA(){
    int i, r, k;
    for(i=0; i<n; i++) SA[i] = i, RA[i] = T[i];
    for(k=1; k<n; k<<=1){
        countingSort(k); countingSort(0);
        tempRA[SA[0]] = r = 0;
        for(i=1; i<n; i++)
            tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
        for(i=0; i<n; i++) RA[i] = tempRA[i];
        if(RA[SA[n-1]] == n-1) break;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int tc; cin >> tc;
    while(tc--){
        cin >> T; n = strlen(T);
        T[n++] = '$'; T[n] = '\0';
        constructSA();
        int cnt = 0;
        for(int i=0; SA[1]+i < n - 1; i++)
            cnt++;
        for(int i=2; i<n; i++){
            bool flag = true;
            for(int j=0; SA[i] + j < n - 1; j++){
                if(SA[i-1] + j >= n - 1 || T[SA[i] + j] != T[SA[i-1] + j]) flag = false;
                if(!flag) cnt++;
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}