Count Unique Substrings

Given a string \( s \) of length \( n \), your task is to compute the number of unique (distinct) non-empty substrings of \( s \). A substring is defined as a contiguous block of characters within the string. Note that although the total number of substrings of a string of length \( n \) is given by the formula \( \frac{n(n+1)}{2} \), some of these substrings might be repeated.

For example, for the string "abc", the unique substrings are: "a", "b", "c", "ab", "bc", and "abc", totaling 6. Your program should process multiple test cases.

inputFormat

The input is read from stdin and it contains multiple test cases. The first line contains a single integer \( T \) denoting the number of test cases. Each of the following \( T \) lines contains a non-empty string \( s \).

outputFormat

For each test case, print a single line (to stdout) containing the number of unique substrings of the given string \( s \).

2
abc
aaa

6
3