Count Distinct Substrings

You are given a string S and your task is to compute the number of distinct substrings of S. A substring is defined as a contiguous sequence of characters within the string. Note that the empty substring is not counted.

For a string of length n, the total number of (not necessarily distinct) non-empty substrings is given by the formula:

[ \frac{n(n+1)}{2} ]

Your job is to count only the distinct substrings among these.

For example, for the string "abcd", there are 10 distinct substrings, while for "aaa" there are 3.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer T representing the number of test cases.
• The following T lines each contain a single string S.

Each test case is processed independently.

outputFormat

For each test case, output a single line to stdout which contains the number of distinct substrings in the input string.

Note: There should be exactly T lines of output corresponding to each test case.

## sample

2
abcd
aaa

10
3

</p>