H. Echoes of Erasure
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$. Let $$$s[i..j]$$$ denote the substring $$$s_i s_{i+1} \ldots s_j$$$.

For every pair of indices $$$(i, j)$$$ with $$$1 \le i \le j \le n$$$, do the following:

  • Take the substring $$$p = s[i..j]$$$ (of length $$$|p| = j - i + 1$$$);
  • Erase $$$p$$$ from $$$s$$$;
  • Concatenate the two remaining parts into the string $$$w := s[1..i-1] + s[j+1..n]$$$, where $$$+$$$ denotes concatenation. Note that either part may be empty.

Let $$$f(i, j)$$$ be the number of occurrences of $$$p$$$ as a substring in $$$w$$$. Here, an occurrence of $$$p$$$ in $$$w$$$ is a position $$$x$$$ such that $$$w[x..(x + |p| - 1)] = p$$$. Occurrences at different positions are counted separately, and they may overlap.

Compute $$$\sum_{1 \le i \le j \le n} f(i, j).$$$

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$) consisting of lowercase Latin letters.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the value of $$$\sum_{1 \le i \le j \le n} f(i, j)$$$.

Example
Input
4
abab
aaaa
aabaab
z
Output
6
15
20
0
Note

In the first test case, $$$s = \texttt{abab}$$$, and the answer is $$$6$$$ — of the ten pairs $$$(i, j)$$$, six contribute one occurrence each and the rest contribute none:

  • $$$(i, j) = (1, 1)$$$: erase $$$\texttt{a}$$$, leaving $$$w = \texttt{bab}$$$, which contains $$$\texttt{a}$$$ once.
  • $$$(i, j) = (1, 2)$$$: erase $$$\texttt{ab}$$$, leaving $$$w = \texttt{ab}$$$, which contains $$$\texttt{ab}$$$ once.
  • $$$(i, j) = (2, 2)$$$: erase $$$\texttt{b}$$$, leaving $$$w = \texttt{aab}$$$, which contains $$$\texttt{b}$$$ once.
  • $$$(i, j) = (3, 3)$$$: erase $$$\texttt{a}$$$, leaving $$$w = \texttt{abb}$$$, which contains $$$\texttt{a}$$$ once.
  • $$$(i, j) = (3, 4)$$$: erase $$$\texttt{ab}$$$, leaving $$$w = \texttt{ab}$$$, which contains $$$\texttt{ab}$$$ once.
  • $$$(i, j) = (4, 4)$$$: erase $$$\texttt{b}$$$, leaving $$$w = \texttt{aba}$$$, which contains $$$\texttt{b}$$$ once.