How many distinct substrings does a given string $S$ have?</p>

For example, if $S =$ abc, $S$ has $7$ distinct substrings: , a, b, c, ab, bc, abc. Note that the empty string and $S$ itself are considered substrings of $S$.

On the other hand, if $S =$ aaa. $S$ has only $4$ distinct substrings: , a, aa, aaa.

입력 형식

The first line of the input file contains $N$, the number of test cases. For each test case, a line follows giving $S$, a string of from $1$ to $5000$ alphanumeric characters.

출력 형식

Your output consists of one line per case, giving the number of distinct substrings of $S$.

예제 입력

2
abc
aaa

예제 출력

7
4