## Problem S4: 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".

### Input

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.

### Output

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) ≤ 1,000.
For all cases, l ≤ 5000.

```2
abc
aaa```

### Sample Output

```7
4```

Point Value: 20 (partial)
Time Limit: 15.00s
Memory Limit: 256M

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (1/3)
watch out for the endl....

• (0/1)
Ok how do we do this problem (without using tries or suffix arrays or any 1337 thing that only brian, hanson, jacob know and are capable of coding becuase they're experienced)?

• (1/0)
It used to be doable using only loops, but I added an extra test case, so now Hanson's loops-only solution gets 180/200.

The suffix array solution is the easiest.

• (0/0)
First you should come up with the loops solution - it's completely doable.
(BTW it seems you changed it to 150/200)

• (0/0)
There can now be up to 5000 characters.
(Now sets/maps will not work - no matter what.)
Again the points will revert to 20, so no one loses (in fact most of you win, since partial marks are now on)

• (1/1)
it worked on my computer.

can someone help :P?

• (0/0)
Notice your memory use: it's getting close to 256MB!
Uncaught exception can mean a lot of things, and one of those things is running out of memory.

• (2/1)
damn these uncaught exceptions