Substrings

문제

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

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

On the other hand, if $S=S\; =$ aaa. $SS$ has only $44$ distinct substrings: , a, aa, aaa.

입력

The first line of the input file contains $NN$, the number of test cases. For each test case, a line follows giving $SS$, a string of from $11$ to $50005000$ alphanumeric characters.

출력

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