Count Distinct Substrings

Given a string, determine the number of distinct substrings that can be extracted from it. A substring is a contiguous block of characters within a string. For example, for the string aaa, the distinct substrings are a, aa, and aaa.

More formally, for a string \( s \) of length \( n \), you are to compute the number of distinct substrings in the set \( \{ s[i:j] \mid 1 \leq i \leq j \leq n \} \).

This problem includes multiple test cases.

inputFormat

The first line of input contains an integer \( T \), the number of test cases.

Each of the next \( T \) lines contains a single string \( s \). The string consists of English letters.

outputFormat

For each test case, output a single line containing the number of distinct substrings of the given string.

## sample

1
abcd

10

</p>