시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB433100.000%

문제

How many distinct substrings does a given string $S$ have?

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$.

제한

50% of test cases will have $l$ (the length of the string) where $l \le 1000$. For all cases, $l \le 5000$.

예제 입력 1

2
abc
aaa

예제 출력 1

7
4