Count Unique Substrings

Given a string S, your task is to count the number of unique substrings in S. A substring is defined as a contiguous sequence of characters within the string. Note that substrings that are identical are counted only once.

Example:

• For S = "abc", the unique substrings are "a", "b", "c", "ab", "bc", and "abc". Thus, the answer is 6.
• For S = "aaa", the unique substrings are "a", "aa", and "aaa". Thus, the answer is 3.

Hint: Use nested loops to generate all possible substrings and a set (or equivalent) to filter out duplicates.

Mathematical Note: The number of total substrings for a string of length n is given by \(\frac{n(n+1)}{2}\), but here we only want the count of unique ones.

inputFormat

The input begins with an integer T (1 \(\leq\) T \(\leq\) 100), denoting the number of test cases. Each of the next T lines contains a non-negative string S consisting of lowercase letters. The length of S is not more than 100.

Note: If S is empty, the answer is 0.

outputFormat

For each test case, output the number of unique substrings in S on a new line.

## sample

2
abc
aaa

6
3

</p>