#include <bits/stdc++.h>   using namespace std;   const int N = 1e5 + 100;   int num;   int sa[N], fir[N], sec[N], t[N];   int height[N], L[N], R[N], st[N];   char c[N];   inline long long SA(int len, char s[]) {     num = 300;     for (int i = 1; i <= num; i++) t[i] = 0;     for (int i = 1; i <= len; i++) ++t[fir[i] = s[i]];     for (int i = 1; i <= num; i++) t[i] += t[i - 1];     for (int i = len; i >= 1; i--) sa[t[fir[i]]--] = i;     for (int k = 1; k <= len; k <<= 1) {       int cnt = 0;       for (int i = len - k + 1; i <= len; i++) sec[++cnt] = i;       for (int i = 1; i <= len; i++)         if (sa[i] > k) sec[++cnt] = sa[i] - k;       for (int i = 1; i <= num; i++) t[i] = 0;       for (int i = 1; i <= len; i++) ++t[fir[i]];       for (int i = 1; i <= num; i++) t[i] += t[i - 1];       for (int i = len; i >= 1; i--) sa[t[fir[sec[i]]]--] = sec[i], sec[i] = 0;       swap(fir, sec);       fir[sa[1]] = 1, cnt = 1;       for (int i = 2; i <= len; i++)         fir[sa[i]] =             (sec[sa[i]] == sec[sa[i - 1]] && sec[sa[i] + k] == sec[sa[i - 1] + k])                 ? cnt                 : ++cnt;       if (cnt == len) break;       num = cnt;     }     int j, k = 0;     for (int i = 1; i <= len; i++) {       if (k) k--;       int j = sa[fir[i] - 1];       while (i + k <= len && j + k <= len && s[i + k] == s[j + k]) k++;       height[fir[i]] = k;     }     int top = 1;     st[top] = 1;     for (int i = 2; i <= len; i++) {       while (top && height[i] < height[st[top]]) R[st[top--]] = i;       L[i] = st[top];       st[++top] = i;     }     while (top) R[st[top--]] = len + 1;     long long ans = 1ll * len * (len + 1) / 2ll;     for (int i = 2; i <= len; i++) {       ans += 2ll * height[i] * (R[i] - i) * (i - L[i]);     }     return ans;   }   int main() {     int t;     scanf( %d , &t);     while (t--) {       scanf( %s , c + 1);       printf( %lld n , SA(strlen(c + 1), c));     }     return 0;   }   