Canadian Computing Competition: 2003 Stage 1, Senior #4
How many distinct substrings does a given string ~S~ have?
For example, if ~S =~
abc, ~S~ has ~7~ distinct substrings:
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:
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~.
2 abc aaa
Output for Sample Input