#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
// return length of common prefix of a, b zero-terminated strings
size_t
string_similarity(char* a, char* b) {
  size_t n = 0;
  while (*a && *b && *a++ == *b++) ++n;
  return n;
}
 
int main() {
  int n = 0;
  if (fscanf(stdin, "%d\n", &n) != 1) { // read number of tests
    perror("fscanf");
    exit(EXIT_FAILURE);
  }
 
 
  const int maxsize = 100002; // + \n \0
  char s[maxsize];
  for (int i = 0; i < n; ++i) {
    if (!fgets(s, maxsize, stdin)) { // read a string to test
      perror("fgets");
      exit(EXIT_FAILURE);
    }
    size_t len = strlen(s);
    if (s[len-1] == '\n') { // chop newline
      s[len-1] = '\0';
      --len;
    }
    uint64_t sum = len; // to support maxsize*(maxsize-1)/2
    for (char* suff  = s+1; *suff; ++suff) { // for all suffixes
      sum += string_similarity(suff, s);
    }
    printf("%" PRIu64 "\n", sum);
  }
  return 0;
}
 

I2luY2x1ZGUgPGludHR5cGVzLmg+CiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KCgovLyByZXR1cm4gbGVuZ3RoIG9mIGNvbW1vbiBwcmVmaXggb2YgYSwgYiB6ZXJvLXRlcm1pbmF0ZWQgc3RyaW5ncwpzaXplX3QKc3RyaW5nX3NpbWlsYXJpdHkoY2hhciogYSwgY2hhciogYikgewogIHNpemVfdCBuID0gMDsKICB3aGlsZSAoKmEgJiYgKmIgJiYgKmErKyA9PSAqYisrKSArK247CiAgcmV0dXJuIG47Cn0KCmludCBtYWluKCkgewogIGludCBuID0gMDsKICBpZiAoZnNjYW5mKHN0ZGluLCAiJWRcbiIsICZuKSAhPSAxKSB7IC8vIHJlYWQgbnVtYmVyIG9mIHRlc3RzCiAgICBwZXJyb3IoImZzY2FuZiIpOwogICAgZXhpdChFWElUX0ZBSUxVUkUpOwogIH0KCgogIGNvbnN0IGludCBtYXhzaXplID0gMTAwMDAyOyAvLyArIFxuIFwwCiAgY2hhciBzW21heHNpemVdOwogIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICBpZiAoIWZnZXRzKHMsIG1heHNpemUsIHN0ZGluKSkgeyAvLyByZWFkIGEgc3RyaW5nIHRvIHRlc3QKICAgICAgcGVycm9yKCJmZ2V0cyIpOwogICAgICBleGl0KEVYSVRfRkFJTFVSRSk7CiAgICB9CiAgICBzaXplX3QgbGVuID0gc3RybGVuKHMpOwogICAgaWYgKHNbbGVuLTFdID09ICdcbicpIHsgLy8gY2hvcCBuZXdsaW5lCiAgICAgIHNbbGVuLTFdID0gJ1wwJzsKICAgICAgLS1sZW47CiAgICB9CiAgICB1aW50NjRfdCBzdW0gPSBsZW47IC8vIHRvIHN1cHBvcnQgbWF4c2l6ZSoobWF4c2l6ZS0xKS8yCiAgICBmb3IgKGNoYXIqIHN1ZmYgID0gcysxOyAqc3VmZjsgKytzdWZmKSB7IC8vIGZvciBhbGwgc3VmZml4ZXMKICAgICAgc3VtICs9IHN0cmluZ19zaW1pbGFyaXR5KHN1ZmYsIHMpOwogICAgfQogICAgcHJpbnRmKCIlIiBQUkl1NjQgIlxuIiwgc3VtKTsKICB9CiAgcmV0dXJuIDA7Cn0K

MgphYmFiYWEKYWE=

2
ababaa
aa