6908번 - Substrings 다국어

문제

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

힌트