Distinct Substrings

Given a string \( s \) consisting of lowercase letters, your task is to find the number of distinct substrings in \( s \). A substring is defined as a contiguous sequence of characters in \( s \). Formally, if \( s \) has a length \( n \), then a substring can be represented as \( s[i:j] \) for any indices \( 0 \le i < j \le n \). Even the empty substring is not counted.

For example, if \( s = \texttt{abc} \), the distinct substrings are: \( \texttt{a}, \texttt{b}, \texttt{c}, \texttt{ab}, \texttt{bc}, \texttt{abc} \), so the answer is 6.

Your task is to implement a function that, given a string \( s \), returns the number of its distinct non-empty substrings.

inputFormat

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

T
s₁
s₂
...
s_T

where:

• T is an integer representing the number of test cases.
• Each of the following T lines contains a non-negative string s (possibly empty) for which you need to count the distinct substrings.

outputFormat

For each test case, output a single integer on a new line representing the number of distinct substrings of the given string.

The output is printed to standard output (stdout).

## sample

2
abc
aaa

6
3

</p>